Big-O Notation: How to Read Any Loop and Know Its Complexity

Your code works. Now someone asks: "what's the time complexity?" You glance at the loop and say "O(n)?" with an upward inflection that makes it sound like a question.

You're not clueless. You're guessing based on vibes, which works fine until someone asks you to justify it. This post fixes that. By the end you'll be able to look at any loop or recursive function and name its complexity class without flinching.

Big-O notation describes how the operation count grows as input size grows, not how fast your code runs on a specific machine. Two programs can both finish in one millisecond, and one of them will take ten years when the input scales. Big-O is how you tell them apart.

Alternative Big O notation slide showing O(1)=O(yeah), O(log n)=O(nice), O(n²)=O(my), O(2^n)=O(no), O(n!)=O(mg!)

The unofficial taxonomy. Apparently O(n!) is where people draw the line.

Why You Can Ignore the Constants

Paul Bachmann introduced the "O" symbol in 1894 to describe how mathematical functions approximate each other for large inputs. Edmund Landau extended it, and it found its way into computer science in the 1950s. The key insight has not changed: at scale, multiplicative constants stop mattering.

The formal definition: f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀. Translated: past some input size, f grows no faster than g, up to a constant multiple.

Two practical rules you will use constantly:

Drop constants. O(3n) is O(n). Whether your loop does one thing per iteration or five, the slope of the growth curve doesn't change.
Drop lower-order terms. O(n² + 5n + 100) is O(n²). As n grows, the dominant term swamps everything else.

So 3n² + 2n + 1000 log n + 5000 collapses to O(n²). Keep only the fastest-growing term.

Think of it like a dinner check. You had water, a side salad, and an $85 wagyu steak. The bill is O(steak). Nobody is analyzing the water.

The Six Curves (and Why the Gap Is Bigger Than You Think)

Six Big-O growth curves on a dark chart: O(1) flat near bottom, O(log n) barely rising, O(n) diagonal, O(n log n) slightly steeper, O(n²) parabolic, and O(2^n) shooting straight up at n≈12

At n=20, these curves have already diverged beyond what the chart can show for O(2^n).

In practice:

Complexity	n = 10	n = 100	n = 1,000
O(1)	1	1	1
O(log n)	3	7	10
O(n)	10	100	1,000
O(n log n)	33	700	10,000
O(n²)	100	10,000	1,000,000
O(2^n)	1,024	~10^30	~10^301

That last row is not a typo. At n = 100, O(2^n) has already produced more operations than there are atoms in the observable universe. O(2^n) algorithms are not slow. They are unusable for any realistic input. Your computer is not working on this problem. It is waiting for physics to cooperate.

O(1): The Same, No Matter What

arr = [10, 20, 30, 40, 50]
first = arr[0]         # O(1)
value = hash_map[key]  # O(1) amortized

Constant time means the operation count stays fixed regardless of input size. Accessing an array by index works because the memory address is computed directly from the base pointer and index. The array length is irrelevant.

Hash map lookups are O(1) amortized: the hash function computes a bucket location in constant time regardless of how many keys are stored. In the pathological case where every key collides into one bucket, lookup degrades to O(n). That's what "amortized" means. The average over all operations is O(1).

Code signal: no loops, no recursion, a fixed number of operations.

O(log n): Every Step Cuts the Problem in Half

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Each step eliminates half the remaining candidates. Four steps handles 16 elements. Thirty handles a billion.

Binary search on a sorted array of n elements: each comparison eliminates half the remaining candidates. After k steps, n / 2^k elements remain. When that reaches 1: n / 2^k = 1, so k = log₂ n.

O(log n) grows almost imperceptibly. log₂(1,000) ≈ 10. log₂(1,000,000) ≈ 20. Doubling the input adds exactly one step. You can binary search a billion-element sorted array in about 30 comparisons.

It feels like cheating. It isn't.

The same pattern appears in balanced binary search trees: each node you visit eliminates one half of the remaining tree, giving O(log n) lookup, insert, and delete.

Code signal: a loop where the search space is divided by a constant factor each iteration. Or a recursive function that only recurses on one branch, not both. See Binary Search: One Invariant to Rule the Search Space for a deep dive.

O(n): One Pass, Proportional Cost

def find_max(arr):
    max_val = arr[0]
    for x in arr:       # n iterations
        if x > max_val:
            max_val = x
    return max_val

Linear time means the work scales directly with input size. Twice the elements, twice the work. This is the baseline for any algorithm that must examine every element at least once. You cannot find the maximum of an unsorted list faster than O(n): you have to check each element.

Two sequential loops are still O(n). O(n) + O(n) = O(2n) = O(n) after dropping the constant. Only nested loops multiply.

Code signal: a single loop running from start to end, or two sequential loops that each run n times.

O(n log n): The Sorting Floor

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Merge sort recursion tree showing an 8-element array splitting into halves at each level, with log n = 3 levels labeled and "n work to merge" annotations on the right

Three levels, eight elements. Each level does n total merge work. Total: n × log n.

Why O(n log n)? Look at the recursion tree:

The tree has log n levels, because the array halves at each level.
At every level, the merge step touches all n elements combined, whether they're in one array or split across many sub-arrays.
Total: log n levels × n work per level = O(n log n).

This is also the theoretical minimum for any comparison-based sort. To sort n elements, you must distinguish among n! possible orderings. Each comparison gives one bit of information. log₂(n!) bits are required, and by Stirling's approximation log₂(n!) ≈ n log n. No comparison sort can do better. Merge sort and heapsort hit this bound exactly.

Code signal: divide-and-conquer structure where you split into two halves (log n depth) and do O(n) work per level to combine results. A loop of n iterations where each iteration itself runs in O(log n) also produces O(n log n).

O(n²): Nested Loops

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # n iterations
        for j in range(n - 1):   # ~n iterations each
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Bubble sort. Nobody deploys it. It exists so algorithms textbooks have something to illustrate O(n²) with, and so interview questions have something to ask you to optimize away from.

An 8×8 grid on a dark background where each cell represents one execution of the inner loop body, with outer loop labeled on the left axis and inner loop on the top axis

8 rows × 8 columns = 64 cells = n² operations. The grid shape is the giveaway.

Two nested loops each running n times means n × n = n² operations. At n = 1,000, that's one million operations. At n = 10,000, it's a hundred million. At n = 100,000, it's ten billion.

Not all nested loops are O(n²). If the inner loop runs a fixed number of times regardless of n (say, always 5 iterations), that's a constant, and the whole thing is O(n). The key is whether both loops scale with n.

Selection sort's inner loop runs n-1, then n-2, then n-3... down to 1. Sum: n(n-1)/2 ≈ n²/2, which is O(n²) after dropping the constant.

Code signal: a loop nested inside another, both of whose iteration counts scale with n.

O(2^n): Every Branch Doubles the Work

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Call tree for fib(4) showing fib(2) computed twice from scratch, with the redundant subtree highlighted in red and annotated as "computed again"

fib(2) gets computed independently in two different branches. At n=50, this recomputation blows up to 2^50 total calls.

Each call to fib spawns two more calls. The call tree has depth n, and at each level the node count roughly doubles. Total nodes ≈ 2^n.

The exact count is O(φⁿ) where φ = (1+√5)/2 ≈ 1.618, because the right-side branches are shallower. But 2^n is the correct upper bound and the right intuition.

fib(50) requires roughly 2^50 ≈ 10^15 calls. On a machine doing 10^9 operations per second, that takes about 11 days. Your laptop will have restarted for OS updates and asked you to restore your tabs before the computation finishes. This is why memoization matters so much. See Recursion Time Complexity: The Tree, the Recurrence, and the Master Theorem for how to analyze these trees rigorously.

Other O(2^n) patterns: generating all subsets of a set (each element is either included or not), and backtracking over all possible states without pruning. For permutations and subset complexity derivations, see Backtracking Time Complexity: Subsets Are O(n·2^n). Permutations Are O(n·n!)..

Code signal: a recursive function that makes two (or more) recursive calls with input sizes close to n, giving a call tree of depth proportional to n.

How to Eyeball Big-O Complexity in 30 Seconds

The pattern-matching cheat sheet:

Single loop, n iterations → O(n)

for i in range(n): ...

Loop that halves the problem each step → O(log n)

while left <= right:
    mid = (left + right) // 2
    # eliminate half

Nested loops, both scaling with n → O(n²)

for i in range(n):
    for j in range(n): ...

Divide-and-conquer: split in half, O(n) merge → O(n log n)

Recursion with 2 calls on ~n-sized input, depth n → O(2^n)

Three things that catch people:

Sequential loops add, nested loops multiply. O(n) + O(n) = O(n). O(n) × O(n) = O(n²).
A loop with an inner binary search is O(n log n). The outer loop runs n times; each iteration does O(log n) work.
What is n? If you loop over an m-element list and binary-search a separate k-element array, the complexity is O(m log k). Two different variables, not one n. Conflating them is the most common Big-O slip in interviews, and the interviewer will notice even if the formula was otherwise right.

The Insight People Miss

Big-O gives you the complexity class, but the constant factor still matters in practice. An O(n log n) algorithm with a huge constant can lose to O(n²) on small inputs. The growth curve chart only shows what happens at the right end.

The question Big-O answers is not "which code is faster right now" but "which code wins at scale." For interview purposes, you need both: state the complexity, then acknowledge when the constant might matter.

Recap

O(1): fixed operations, no scaling
O(log n): problem halves each step
O(n): single pass through all elements
O(n log n): log n levels, O(n) work per level; the sorting minimum
O(n²): nested loops, both scaling with n
O(2^n): two recursive calls of equal size, depth n
Drop constants, drop lower-order terms, keep only the dominant term
Sequential loops add. Nested loops multiply.

Coding interviews expect you to state and justify complexity without being prompted. If you want to practice doing that under pressure, out loud, with immediate feedback, SpaceComplexity runs voice-based mock interviews where complexity analysis is scored as part of the rubric.