What Is Big O Notation? A Cheat Sheet with Examples

Big O notation describes how an algorithm's running time or memory usage grows as the input gets bigger. O(1) means the cost stays constant no matter the size, O(n) means it grows in direct proportion to the input, and O(n²) means it grows with the square of the input — which is why scanning a million rows once is instant but comparing every row against every other row is not. The "O" stands for "order of," and the expression inside names the growth rate that dominates once n gets large.

The common complexities, ranked fastest to slowest

Almost everything you meet in practice falls into one of seven classes. The table below ranks them with a concrete example each, plus a rough sense of what each costs at n = 1,000 so the gaps feel real rather than abstract.

The jump that matters most in daily work is the one from O(n log n) to O(n²): at a thousand items it is the difference between ten thousand operations and a million. That is why swapping a nested loop for a hash-table lookup is the single most common real-world optimization, and why sort implementations are such a frequent interview topic — see the sorting algorithms reference for the complexity of each classic sort.

How to estimate Big O in three steps

You rarely need a formal proof. Walk through code with these three rules and you will land on the right class nearly every time.

1. Count operations in terms of n. A single loop over n items is n steps. Two separate loops are n + n. A loop inside a loop is n times n.
2. Keep only the fastest-growing term. In n² + n + 5, the n² term dwarfs everything else as n grows, so the answer is O(n²).
3. Drop constants and coefficients. O(2n) is O(n); O(n/2) is O(n); O(5) is O(1). Big O describes the shape of the curve, not its exact height.

Three tiny examples make the rules concrete:

# O(n) — one pass, work scales with the list
total = 0
for x in items:
    total += x

# O(n^2) — nested loops multiply
for a in items:
    for b in items:
        compare(a, b)

# O(log n) — halve the search space each step
while lo < hi:
    mid = (lo + hi) // 2
    if values[mid] < target:
        lo = mid + 1
    else:
        hi = mid

A common trap is hiding work inside a helper call: testing membership in a plain list is itself an O(n) scan, so calling it inside a loop silently builds an O(n²) algorithm. Converting the list to a set first — one O(n) pass — drops the whole thing back to O(n). The same pattern shows up in databases, where a nested-loop join behaves like O(n × m); the SQL join types guide shows when the planner picks that strategy and when it can do better.

Cheat sheet: data structure operation costs

Algorithm choice gets the attention, but data structure choice decides the complexity of the operations your algorithm repeats. These are the average cases worth memorizing, with worst cases noted where they bite.

Two footnotes save real debugging time. First, hash tables degrade toward O(n) under heavy collisions, which is why serious implementations resize aggressively and some languages randomize hashing. Second, "amortized O(1)" for appending to a dynamic array means occasional resizes cost O(n) while the average per append stays constant — fine for batch work, occasionally surprising in latency-sensitive loops.

Big O vs Big Theta vs Big Omega: what is the difference?

Big O is an upper bound: saying f(n) is O(g(n)) means f grows no faster than g, so calling binary search O(n) is technically true but uselessly loose. Big Omega is the matching lower bound — f grows at least as fast as g — and Big Theta is the tight bound where both hold at once, pinning the growth rate exactly. In interviews and documentation, "Big O" almost always means the tight bound unless someone says otherwise, so quicksort's "O(n log n)" is really its average-case Theta with an O(n²) worst case. For the formal definitions, see the complexity classes reference; the same data is fetchable as JSON at complexity-analysis.json.

FAQ: what Big O should I aim for?

Is O(n log n) good? Usually yes. It is the best any comparison-based sort can do, and for most application code it scales comfortably into the millions of items. Treat it as the default meaning of "efficient."

When is O(n²) acceptable? When n stays small — under a few thousand — or the quadratic code runs rarely. An O(n²) check over a fifty-item config list is simpler and faster in wall-clock terms than fancier machinery. Problems start when small inputs quietly grow: today's two hundred rows become next year's two hundred thousand.

Does Big O cover memory too? Yes, the notation applies to space as well as time. Mergesort is O(n log n) time but O(n) extra space, while heapsort matches the time with O(1) extra space — a tradeoff worth knowing when memory is tight.

Do constants ever matter more than the class? Absolutely, at small n. An O(n) algorithm with a huge constant — heavy setup, cold caches — can lose to an O(n²) one on small inputs. Big O answers "what happens as n grows," not "what is fastest at n = 10." Measure when it matters.