# Big-O Notation

Describing how resource use grows with input size, discarding constants and lower-order terms to expose scaling behaviour.

**Leads to:** Balanced Trees and B-Trees, Data Mining, Microservice Cost Tradeoffs, Space-Time Tradeoffs, Text Mining at Scale

**Rests on nothing.** A place to start.

*Machine Learning · Algorithms and Complexity*


## Why learn this

You need Big-O notation to predict how a program's speed will change as the amount of data it processes grows. Imagine you are building a system that retrieves documents from a database. If the database has 1,000 records, it might respond instantly. But if it grows to 1,000,000 records, will the response time double, or will it become unusable? Big-O gives you a quick way to answer that question without running tests on every possible data size. It is the tool that lets you compare two different methods for solving a problem and choose the one that remains fast as your users and their data expand. Without this understanding, you cannot judge why a simple loop nested inside another loop slows down so dramatically or how to select an approach that scales reliably.


## The intuition

Imagine you are a chef preparing meals for a party. The amount of time it takes you to cook depends on the number of guests. If you have to chop each vegetable for each guest, then doubling the guests doubles your chopping time. That is called linear growth: time grows in direct proportion to the number of guests. For example, if chopping vegetables for 10 guests takes 10 minutes, it will take roughly 20 minutes for 20 guests.

But consider a different task: arranging seating where you must compare every guest with every other guest to ensure compatibility. If you have 2 guests, you have 1 comparison. With 4 guests, you have 6 comparisons. With 8 guests, you have 28 comparisons. Doubling the number of guests more than doubles the work; it causes the work to grow much faster. This is quadratic growth.

Big-O notation is a way to describe this relationship between input size and time (or memory) without getting bogged down in exact details like 'the chef cooks at 3 miles per hour' or 'the kitchen has one stove.' It focuses on the shape of the curve as the input gets very large. It asks: if I double the input, what happens to the time?

If time doubles, we say it is O(n) — linear growth.
If time quadruples (roughly), we say it is O(n^2) — quadratic growth.
If time doesn't change at all regardless of input size, we say it is O(1) — constant time. That is the whole idea: it describes growth patterns, not absolute speed.


## An analogy

Think of Big-O as the story of a photocopier in an office. Suppose you have a stack of pages to copy. If you copy each page one at a time, the time it takes is directly proportional to the number of pages: copying 10 pages might take 10 minutes, and copying 20 pages will take 20 minutes. That is linear growth, or O(n).

Now suppose instead of copying each page individually, you have to compare each page with every other page in the stack to check for identical content. With a stack of 10 pages, that requires checking 45 pairs. With a stack of 20 pages, that requires checking 190 pairs. Doubling the number of pages roughly quadruples the work required. That is quadratic growth, or O(n^2).

But there is a third scenario: you have a huge stack of pre-printed forms and you just need to find one specific blank sheet from a known location at the top. You always take the same 30 seconds to grab it, regardless of whether the stack has 10 pages or 10,000 pages. That is constant time, or O(1).

The photocopier analogy shows that Big-O is not about how fast the machine is (that is the constant factor) but about how the workload grows as the stack grows. One important limitation of this analogy is that real computer hardware has memory layers: sometimes a method that looks slower in theory is actually faster in practice because it fits into fast, small storage spaces called cache. So Big-O is a guide to the shape of the curve, not a guarantee of exact performance.


## Definition

Big-O notation is a way to describe how the time or memory required by a procedure grows as the size of its input grows, ignoring fixed constants to focus on the dominant pattern of scaling.


## How it connects

This concept is the foundation for Algorithms and Complexity. It connects directly to Binary Search, a method that finds items in sorted lists by repeatedly halving the search area, achieving very fast performance known as logarithmic time. It also connects to Dynamic Programming, a technique that solves complex problems by breaking them into overlapping sub-problems to avoid redundant calculations.


## The mathematics

Big-O notation draws from a branch of mathematics called 'asymptotic analysis', which is about what happens when numbers get extremely large. You don't need any calculus — just arithmetic and an understanding of ratios. The core idea is to describe how a quantity (like time) changes when the input size changes. We usually talk about the input size, which we call 'n'. For each algorithm, there is a relationship between n and the number of basic operations performed. Big-O notation takes that relationship and simplifies it: it keeps only the term that grows the fastest as n becomes huge, and it drops any constant multipliers. For example, if the number of operations is 5n^2 + 3n + 10, for very large n, the 5n^2 term dominates; the 3n and 10 become negligible in comparison. So we say the algorithm is O(n^2). This is not an exact count — it's an upper bound on the growth rate. The three stages of mathematics are: first, you understand what 'growth rate' means; second, you work a specific example by hand with numbers; and third, you write the formula as shorthand for what you did.

Formally, a function f(n) is O(g(n)) if there exist positive constants c and n₀ such that for all n ≥ n₀, f(n) ≤ c * g(n). In practice, you take the highest-order term of f(n), drop its coefficient, and that gives you g(n). For example, if f(n) = 3n^2 + 5n + 2, then g(n) = n^2, and we write f(n) = O(n^2).


## A worked example

```
Suppose we have an algorithm that, for an input of size n, performs 3n^2 + 5n + 2 operations. Let's compute exactly what that means for n = 1, 2, 3, 4, and then see how it behaves as n gets large.

Step 1: For n=1: 3*(1)^2 + 5*1 + 2 = 3 + 5 + 2 = 10   # With 1 item, we do 10 operations.
Step 2: For n=2: 3*(2)^2 + 5*2 + 2 = 12 + 10 + 2 = 24   # Doubling n from 1 to 2 more than doubled the operations (10 to 24).
Step 3: For n=3: 3*(3)^2 + 5*3 + 2 = 27 + 15 + 2 = 44   # As n increases, the n^2 term grows faster than the n term.
Step 4: For n=4: 3*(4)^2 + 5*4 + 2 = 48 + 20 + 2 = 70   # Notice the n^2 term is already dominating: 48 out of 70 is about 69%.
Step 5: For n=1000: 3*(1000)^2 = 3,000,000; 5*1000 = 5,000; 2; total ≈ 3,005,002   # The n^2 term is 3,000,000, which is over 99.8% of the total. The 5n and 2 are negligible.

Result: The dominant term is 3n^2. Since constants don't affect the growth rate, we say this algorithm is O(n^2). Even though the coefficient is 3, the growth pattern is quadratic: when n doubles, the time roughly quadruples.
```


## From scratch, in Python

```python
def count_operations_linear(n):
    """Simulates a linear algorithm: does n operations."""
    count = 0
    for i in range(n):
        count += 1  # one operation per item
    return count

def count_operations_quadratic(n):
    """Simulates a quadratic algorithm: does n*n operations."""
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1  # one operation for each pair (i, j)
    return count

# Test with small and large n
for n in [1, 2, 3, 10]:
    print(f"n={n}: linear={count_operations_linear(n)}, quadratic={count_operations_quadratic(n)}")

# Show how doubling n affects the count
n = 10
linear_ops = count_operations_linear(n)
quadratic_ops = count_operations_quadratic(n)
print(f"For n={n}: linear ops = {linear_ops}, quadratic ops = {quadratic_ops}")
print(f"For n={2*n}: linear ops = {count_operations_linear(2*n)}, quadratic ops = {count_operations_quadratic(2*n)}")
print("Note: linear doubles, quadratic quadruples")
```


## What the code does

The code defines two functions, one that simulates a linear algorithm and one that simulates a quadratic algorithm. It uses `for` loops, which you may not have seen before — a `for` loop repeats a block of code a certain number of times. `range(n)` gives you the numbers 0, 1, 2, ..., n-1, so `for i in range(n)` runs the block n times. The linear function has one loop, so it does n operations. The quadratic function has a loop inside another loop: for each value of i, the inner loop runs n times, so total operations are n * n = n^2. The output shows that doubling n from 10 to 20 makes the linear count double (10 to 20) but the quadratic count quadruple (100 to 400). This is the essence of Big-O: the quadratic algorithm grows much faster.


## Common misconceptions

**Big-O is about speed** — If one algorithm is O(n) and another is O(1), then the O(1) algorithm is always faster.

Big-O describes growth, not absolute speed. An O(1) algorithm might take 10 milliseconds per operation, while an O(n) algorithm might take 0.1 milliseconds per operation. For small n, the O(n) algorithm could be faster. Big-O only tells you what happens as n gets very large. In fact: Big-O describes how the time or memory grows with input size, not the absolute speed at a given size. Constants and lower-order terms are ignored, so an O(n) algorithm with a small constant can beat an O(1) algorithm with a huge constant for small inputs.

**O(n^2) is always worse than O(n)** — Any algorithm that is O(n^2) is always worse than one that is O(n).

For small n, the O(n^2) algorithm might be faster if it has a smaller constant factor. For example, an algorithm that does 2n operations (O(n)) might be slower than one that does n^2/1000 operations (O(n^2)) when n is less than 2000. Big-O tells you about the long-term trend, not the crossover point. In fact: Big-O is about asymptotic behaviour. It is only guaranteed to hold for sufficiently large n. In practice, you measure and profile to find the crossover point, which is exactly what space-time tradeoffs are about.

**Big-O tells you the exact number of operations** — If an algorithm is O(n^2), it means it does exactly n^2 operations.

Big-O discards constants and lower-order terms. An algorithm could do 3n^2 + 5n + 2 operations, or 0.5n^2 + 100n operations, and both are O(n^2). It is an upper bound on the growth rate, not an exact count. In fact: Big-O is a classification of growth, not an exact count. It tells you the dominant term, but the constant multiplier and lower-order terms are hidden.

**Big-O is only for time** — Big-O only describes how fast a program runs.

Big-O also applies to memory (space). An algorithm might be fast but use a huge amount of memory, which is also described with Big-O. For example, a recursive Fibonacci algorithm is O(2^n) time and O(n) space if you count the call stack, but a dynamic programming version is O(n) time and O(n) space. Both time and space matter. In fact: Big-O applies to both time complexity and space complexity. When designing systems, you often need to trade one off against the other — that's the space-time tradeoff you have in your library.

**Big-O is the only thing that matters** — Once I know an algorithm is O(n log n), I don't need to worry about anything else.

As your library notes, constants occasionally dominate in practice, especially with memory hierarchy effects. An O(n log n) algorithm that causes many cache misses can be slower than an O(n^2) algorithm that fits in cache. For small inputs, the constant factor is often more important than the asymptotic complexity. In fact: Big-O is a first-line filter, but you must also consider constants, input size, and hardware effects. This is why profiling and benchmarking are essential.


## In short

Big-O notation describes how the time or memory used by an algorithm grows as the input size grows, ignoring constants and lower-order terms. The most common growth rates, from fastest to slowest, are O(1) (constant, independent of input), O(log n) (logarithmic, grows very slowly), O(n) (linear, direct proportion), O(n log n) (common in efficient sorts), O(n^2) (quadratic, doubles -> quadruples), and O(2^n) (exponential, infeasible for large n). Always ask: if I double the input, what happens to the work? Constant, double, or quadruple? That's Big-O.


## Where this is used

Big-O notation is used everywhere in AI systems, often behind the scenes, to decide whether an algorithm is feasible. In large language models (LLMs), the transformer architecture has a self-attention mechanism that compares every token in the input with every other token. If the input has n tokens, the number of comparisons is roughly n^2 — O(n^2). This is why LLMs have a context window limit: doubling the input length quadruples the computation. When you read about models struggling with long documents, this is why. Engineers constantly look for ways to reduce this complexity, such as using sparse attention or linear attention, which try to get closer to O(n). In small language models running on phones or laptops, the constraint is more severe. Memory and battery are limited, so you might choose an algorithm with worse Big-O but better constant factor, because the input sizes are small. For example, a simple loop over a vocabulary of 50,000 words might be O(n) and fine, whereas a more complex algorithm with O(n log n) might be slower in practice because of overhead. This is a real trade-off you'll meet when you study Space-Time Tradeoffs. In retrieval-augmented generation (RAG), you embed documents and queries into vectors, then find the closest matches. The naive way is to compare the query vector with every document vector — O(n) per query, where n is the number of documents. For millions of documents, that's too slow. So engineers use approximate nearest neighbour (ANN) indexes that search in O(log n) or even O(1) time, accepting a small loss in accuracy. This is a direct application of Big-O: choose an algorithm with better scaling even if the constant factor is larger. In agentic systems that plan and call tools, an agent often explores multiple paths. The search space can grow exponentially — O(2^n) — if you try every combination of actions. Agents use heuristics, pruning, and other tricks to avoid this explosion, and Big-O analysis tells you when an approach is doomed. In everyday applied machine learning, you often have to choose between algorithms for clustering, sorting data, or computing distances. For example, k-nearest neighbours (kNN) classification is O(n) per prediction (or O(n^2) if you're not careful), which is fine for small datasets but terrible for large ones. This is why you use approximate methods or train a model that has O(1) inference time. When developers implement a new feature, they write loops that search through lists; Big-O tells them to use a hash table (O(1) lookups) instead of a list (O(n) lookups) when the data is large. If they get this wrong, the AI system becomes unusably slow. That's why Big-O is not just academic — it's the difference between a prototype that works on a toy dataset and a system that works on real-world data.


---

Read this on the web: https://basavapurushottam.com/learn-ai/big-o-notation
