Big-O Complexity, Explained With Real Code

Big-O notation gets memorized as trivia — "hash lookups are O(1)" — without the underlying skill: looking at any function and knowing how it scales. That skill is what interviews probe and what separates engineers whose systems survive growth from those whose fall over at 10x data. This post builds the intuition from actual code, not formulas.

What Big-O actually measures#

Big-O describes how runtime grows as input grows — deliberately ignoring constants and hardware. An operation taking 2n steps and one taking 5n are both O(n): different speeds, same shape of scaling. The notation answers one question: when input doubles, what happens to time?

Class	Input doubles...	Feel
O(1)	nothing changes	instant, always
O(log n)	adds a few steps	barely notices
O(n)	doubles	doubles
O(n log n)	slightly more than doubles	still fine
O(n²)	quadruples	hurts
O(2ⁿ)	becomes astronomical	unusable past tiny inputs

Reading complexity from code#

O(1) — constant#

def first(items):
    return items[0]        # index access
def has_key(d, k):
    return k in d          # hash lookup (average)

No loops over input; work is fixed regardless of size. Also constant: arithmetic, object attribute access, append to a dynamic array.

O(log n) — halving#

def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_items[mid] == target: return mid
        if sorted_items[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

The signature of logarithmic code: each step discards half the remaining input. A million items need ~20 steps; a billion, ~30. Any divide-and-conquer structure (balanced trees, binary search) carries this shape.

O(n) — touching everything once#

def total(prices):
    s = 0
    for p in prices:      # single pass
        s += p
    return s

One loop over n items. Crucially, hidden loops count too: sum(prices) is O(n); x in list is O(n). Two sequential loops are still O(n) — O(2n) simplifies to O(n) because constants don't matter to the shape.

O(n log n) — sort-shaped#

def top_k(products, k):
    products.sort()                    # O(n log n)
    return products[:k]

Efficient general sorting's class — typically "an O(log n) process applied across n elements" (merge sort, heap operations). When you see sorting followed by a single pass, this is you.

O(n²) — everything against everything#

def has_duplicate_pair(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Nested loops over the same input. Each loop is n; nested multiplies. Also beware disguised quadratic code:

def build(items):
    out = []
    for x in items:
        if x in out:        # 'in' on a LIST is O(n)!
            continue
        out.append(x)
    return out              # whole function: O(n²)

Same intent with a set instead of list drops it to O(n) — structure choice is algorithm choice.

O(2ⁿ) — exponential blowup#

def fib_naive(n):
    if n < 2: return n
    return fib_naive(n-1) + fib_naive(n-2)   # recomputes endlessly

Each call spawns two more: n=40 already means over a billion calls. The fix — caching subresults (memoization) — collapses it to O(n), which is exactly the dynamic programming insight in miniature.

Rules for analyzing anything#

1. Loops multiply when nested, add when sequential
2. Function calls count their own cost — know your library (sort, in, slicing all carry prices)
3. Drop constants and smaller terms: O(n² + n) → O(n²)
4. Different inputs get different variables: two arrays → O(n + m), never O(n²)
5. Space complexity works identically — extra memory allocated scales the same way (recursive call stacks count!)

The misconception worth killing#

O(1) doesn't mean fast; it means scaling-invariant. A "constant-time" operation taking 500ms loses to an O(n) scan over small inputs every time. Big-O predicts behavior at scale — which is why real optimization starts by profiling actual bottlenecks before reaching for asymptotic wins. Interviews test whether you can predict scaling; production rewards knowing when that prediction matters (measure first).

Fluency target: read any unfamiliar function and state its complexity within thirty seconds. Drill it on every codebase you touch for a week — the reflex forms faster than you'd expect.

Related: pattern cheat sheet · data structures guide · 12-week plan