Big-O Analysis in Practice

Reading nested loops#

Every page so far has stated the Big-O of the algorithm being taught — this page is about how to work that out yourself, on code you've never seen labeled before. The core technique: count how many times the innermost line of code actually executes, as a function of the input size, then drop constants and lower-order terms. That count is the Big-O.

def example_a(arr):              # O(n)
    total = 0
    for x in arr:
        total += x
    return total

def example_b(arr):              # O(n^2) — a nested loop over the same data
    pairs = []
    for x in arr:
        for y in arr:
            pairs.append((x, y))
    return pairs

def example_c(arr):              # O(n) — two separate loops, not nested, so they ADD, not multiply
    total = sum(arr)             # O(n)
    maximum = max(arr)           # O(n)
    return total, maximum        # O(n) + O(n) = O(2n) -> O(n)

def example_d(n):                # O(log n) — the loop variable is halved every iteration
    count = 0
    while n > 1:
        n = n // 2
        count += 1
    return count

• example_a: one loop over n elements, one unit of work each → O(n).
• example_b: for each of the n outer-loop elements, the inner loop runs n more times → n × n total operations → O(n²). This is the exact shape flagged all the way back in the introduction's duplicate-checking example.
• example_c: two loops that run one after the other, not nested inside each other — their costs add (O(n) + O(n) = O(2n)), and constants get dropped, leaving O(n). This is the single most common mix-up when reading someone else's code: only nested loops multiply; sequential loops just add.
• example_d: n gets divided by 2 every iteration. After k iterations, n has been divided by 2^k; the loop stops once 2^k >= n, i.e., once k >= log2(n) → O(log n) iterations total — the same shrinking-by-half shape that makes binary search fast.

Reading recursive calls: recurrence relations, intuitively#

For a recursive function, two questions get you most of the way to its Big-O without needing to formally derive anything: how many recursive calls does each invocation make, and how much does the input shrink each time?

The pattern worth internalizing: shrinking the input by half keeps the recursion tree shallow (only O(log n) levels deep) regardless of how many calls happen at each level — that's what keeps binary search at O(log n) and what keeps merge sort's recursion itself cheap, even though merge sort's combine step (O(n) of merging work, repeated at every one of those O(log n) levels) is what actually pushes its total up to O(n log n). By contrast, shrinking the input by only a constant amount, combined with more than one recursive call per invocation, causes the total number of calls to multiply out across depth — naive Fibonacci's two calls per invocation, repeated across n levels of depth, produces roughly 2ⁿ total calls, which is exactly the exponential blowup the recursion page warned about. The single biggest factor separating a merge-sort-style recursion from a Fibonacci-style one isn't "how many recursive calls happen" — it's whether the input shrinks fast enough (by a fraction) to keep the recursion shallow despite that branching.

Amortized analysis: why a dynamic array's append is O(1)#

Python's list is a dynamic array: internally, it's backed by a fixed-size array that gets reallocated — a new, larger array is allocated and every existing element is copied into it — whenever it runs out of room. That reallocation is an O(n) operation, which makes it tempting to conclude append must be O(n) in the worst case. But that expensive step only happens occasionally, and the trick that makes it cheap on average is that each resize roughly doubles the array's capacity, buying a long stretch of cheap O(1) appends before the next resize is needed at all.

Here's the arithmetic behind that claim. Suppose the array's capacity doubles every time it fills up: capacity 1 → 2 → 4 → 8 → .... Across n total appends, the total amount of copying work done by all resizes combined is 1 + 2 + 4 + ... + n/2 — a geometric series that sums to roughly n, not n². Spread that total O(n) copying cost evenly across all n appends, and each append's share of the copying cost works out to O(1) — even though any single append that happens to trigger a resize does, in that one moment, cost a real O(n).

This is the precise meaning of amortized O(1): not every individual operation is cheap, but the total cost of any long sequence of operations, divided by how many operations there were, stays bounded by a constant. It's a genuinely different claim from worst-case-per-operation analysis (which would have to say "O(n), because of the rare expensive resize") — both statements are true about the same function; they're just answering different questions. ("Is this one call fast?" versus "Is a long run of these calls fast, on average?")

A few more snippets, worked through#

def snippet_1(matrix):                    # matrix is n x n
    total = 0
    for row in matrix:
        for value in row:
            total += value
    return total

Two nested loops, but over an n x n matrix specifically — the outer loop runs n times, and the inner loop runs n times for each row, visiting every one of the n² cells exactly once. O(n²), not O(n) — the fact that it's "just adding numbers up" doesn't matter; what matters is how many times that addition actually executes.

def snippet_2(arr):
    arr.sort()                            # O(n log n)
    return arr[0], arr[-1]                # O(1)

Sorting dominates everything else in this function — O(n log n) plus O(1) is still O(n log n), since the lower-order term contributes nothing once n is large. (If all you need is the min and max, a single O(n) pass without sorting would actually be the better choice here — sorting the whole array is overkill just to read its two ends.)

def snippet_3(arr, target):
    for i in range(len(arr)):
        if binary_search(arr[:i], target) != -1:   # O(log i) search, but O(i) slice copy
            return i
    return -1

This one hides a trap: binary_search itself is O(log i), but arr[:i] copies i elements to create the slice before the search even begins — an O(i) cost that dominates the O(log i) search sitting right next to it. Across the outer loop, that adds up to O(n²) total, not the O(n log n) it might look like at a glance. The fix would be to search the original array directly with explicit bounds instead of slicing a new one every iteration.

Common mistakes#

• Multiplying the complexities of sequential loops. Two separate, back-to-back O(n) loops are O(n) total, not O(n²) — only nested loops multiply.
• Assuming any recursive function with more than one recursive call is automatically exponential. It depends critically on whether the input shrinks by a constant amount or by a fraction — shrinking by half keeps the recursion tree shallow no matter how many branches happen at each level, as merge sort shows.
• Judging amortized complexity from a single worst-case operation instead of the average across a full sequence — one expensive resize doesn't mean every append is expensive.
• Ignoring the hidden cost inside a built-in operation. arr.append(x) is O(1) amortized, but arr.insert(0, x) is O(n) — inserting at the front of a Python list requires shifting every existing element over by one position, a cost that's easy to overlook since both look like simple one-line operations.