Intro to Big-O Notation

When we ask 'how fast is this code?' we don't really mean wall-clock seconds — those depend on your machine, the JIT, what else is running. We mean: as the input gets bigger, how does the work scale? Big-O is a way to talk about that scaling without committing to a specific machine.

O(f(n)) means: for large enough n, the work is at most a constant times f(n). Constants and lower-order terms get dropped. So 3n + 50 is O(n). And n² + 1000n is O(n²) — the n² dominates once n is big enough.

From fastest to slowest:

• O(1) — constant. Looking up a value in a hash map.
• O(log n) — logarithmic. Binary search.
• O(n) — linear. One pass through the list.
• O(n log n) — linearithmic. Good general-purpose sorts (mergesort, heapsort, Timsort).
• O(n²) — quadratic. Two nested loops over the same input.
• O(2ⁿ) — exponential. Naive recursive Fibonacci, brute-force subsets.

The practical takeaway: once you cross from polynomial (O(n^k)) into exponential, even modest input sizes become intractable. An $O(2^n)$ algorithm with $n=40$ is already over a trillion operations.

For the same n, here's how the work piles up.

If you walk through the input once, doing constant work per element, you're at O(n).

for item in items:
    process(item)

Doubling the input doubles the work. This is the dream for most problems — predictable, friendly, and hard to beat without exploiting structure (sortedness, hashability, etc.).

A subtle variant: what if process itself is O(log n)? Then the total is $O(n \log n)$. Always trace into the function bodies — "the loop is O(n)" is a lie if the loop body isn't O(1).

Two nested loops over the same input is the classic O(n²).

for a in items:
    for b in items:
        compare(a, b)

Doubling the input quadruples the work. The math: $T(2n) = (2n)^2 = 4n^2 = 4 \cdot T(n)$.

Fine for n=100, painful for n=100,000. The classic fix is a hash map: precompute lookups so the inner loop becomes O(1), dropping the whole thing to O(n).

Each iteration throws away half the remaining input. Binary search is the canonical example: check the middle, then recurse on the half that could contain the answer. With 1,000,000 items, you finish in about 20 steps.

When in doubt, count the loops and what each one does.

• One loop over n items, constant work inside → O(n).
• Loop that halves n each time → O(log n).
• One loop containing another over the same data → O(n²).
• A loop that calls a function which itself loops over the data → multiply: O(n) × O(n) = O(n²).
• Two sequential loops, each O(n) → O(n) + O(n) = O(2n) = O(n). Constants drop.

The last point catches people out: sequential ≠ nested. Reading the input twice is still O(n). It's only when one loop sits inside another that you multiply.

Big-O describes the worst case unless we say otherwise. There's also:

• $\Omega(f(n))$ — a lower bound. The work is at least proportional to $f(n)$ for large $n$.
• $\Theta(f(n))$ — a tight bound. Same as O and Ω simultaneously. The work grows exactly like $f(n)$.

For most day-to-day work, O(...) implicitly means worst case, which is what you should optimize for unless you have strong evidence about the input distribution. Quicksort is a classic counter-example: $O(n^2)$ worst case but $\Theta(n \log n)$ on random input — which is why it ships in standard libraries despite the scary worst case.

Two O(n) algorithms can differ by 100x in real-world speed because of cache behavior, branch prediction, allocations, etc. Big-O is the first filter — it tells you whether your idea is even in the right neighborhood. Profiling tells you the rest.