How we measure cost: Big-O and complexity

What this chapter covers

Every other chapter in this book compares things: this structure against that one, the hand-rolled version against the library. To compare them honestly you need a way to say how expensive an algorithm is that doesn't depend on your laptop, your language, or the mood of the operating system that afternoon. That way is Big-O. It measures how the work grows as the input grows, and it is the single most useful idea in this whole field. Get it, and the rest of the book is a series of applications. So we start here, before any data structure, and build the measuring stick everything else is measured with.

A bit of history

The notation is older than computers. Paul Bachmann introduced the big-O symbol in 1894 in a book on number theory, and Edmund Landau spread it through analysis a few years later — which is why mathematicians still call it Landau notation. For decades it lived in proofs about how fast error terms shrink, nothing to do with programs.

Donald Knuth dragged it into computer science. In a 1976 note titled "Big Omicron and Big Omega and Big Theta" he argued that the same notation was exactly what programmers needed to talk about running time without drowning in hardware details, and he standardized the O, Ω, and Θ we use today. By the time the first volume of his Art of Computer Programming was widely read, "what's the Big-O of that?" had become the normal way to ask whether an algorithm would survive contact with real data.

The intuition

Forget seconds for a moment. Count operations instead, and count them as a function of the input size, which we always call n.

If a function does the same fixed amount of work no matter how big the input is, it's constant — grabbing the first element of a list takes one step whether the list has ten items or ten million. If it does one pass over the input, the work tracks n: double the input, double the work. If it can throw away half the remaining input at every step, the work is the number of times you can halve n before nothing is left, which is tiny — that's the logarithm. And if it looks at every element against every other element, the work is n times n, which gets ugly fast.

Big-O keeps only the term that dominates as n grows and drops the constants. A loop that runs 3n plus 7 times is O(n): once n is large, the 3 and the 7 don't change the shape of the curve. That sounds like throwing away information, and it is — deliberately. The constant is what a faster language or a better CPU buys you. The shape is what the algorithm itself costs, and the shape is what decides whether your program finishes.

Complexity: how it scales

Here are the classes you meet over and over, from cheapest to most dangerous:

Constant time, $O(1)$, is the ceiling — nothing beats doing a fixed amount of work. Logarithmic time, $O(\log n)$, is almost as good: at n a billion, $\log_2 n$ is only about thirty. Linear time, $O(n)$, is the honest cost of looking at all your data once. Then $O(n \log n)$, the price of a good sort, still very livable. After that it turns: $O(n^2)$ quadruples when the input doubles, and $O(2^n)$ doubles when the input grows by a single element.

Some of these come from a recurrence — a cost defined in terms of itself. Merge sort splits its input in half, sorts each half, and merges the results, which is exactly:

The chart below plots the operation counts for each class as n grows. The y-axis is logarithmic, because otherwise the $O(2^n)$ line would flatten everything else into the floor:

That's the theory. The point of this book is that the theory shows up in the wall clock too. Here are the same shapes, but now measured — one real function per class, timed on inputs from 128 up to 2048 elements, again on a log y-axis:

The measured lines have the same ordering as the theoretical ones. The constant line sits flat on the floor, the quadratic line climbs steepest, and the gaps between them widen exactly as Big-O says they should.

What it's good at, what it isn't

Big-O is the right tool when you want to know if an algorithm scales — whether it will still work when the input is ten or a hundred times bigger than your test case. It answers that better than any benchmark, because it ignores the noise a benchmark can't: the constant factors that change with hardware, cache, and compiler. Two engineers on different machines will disagree about milliseconds and agree about Big-O.

What it hides is exactly those constants, and sometimes the constants are the whole story. An $O(n)$ algorithm with a huge constant can lose to an $O(n^2)$ one on every input you'll ever actually run — which is why the standard library uses insertion sort, an $O(n^2)$ algorithm, for short arrays. Big-O is also an asymptotic claim, about behavior as n heads to infinity; for the small n in front of you it can be misleading. Treat it as the first question you ask, never the last. It tells you which algorithms to rule out; measuring tells you which of the survivors to ship.

The data, or the inputs

The inputs in this chapter are deliberately boring: lists of integers. What matters is their size, not their content, because Big-O is a statement about size. The from-scratch functions each take a representative shape of input — a sorted list for the searches, an unsorted one for the sort, a plain list for the nested-loop count — and the trace code runs them at a range of sizes so we can watch the cost curve bend.

The one input worth looking at up close is the sorted array the two searches run on, because that is where you can actually see the difference between a linear cost and a logarithmic one.

Build it, one function at a time

Start with the cheapest thing there is. Constant time does a fixed amount of work regardless of n:

def first(values):
    """O(1): touch one element, no matter how long the list is.

    A million elements or ten, this does the same single indexing operation.
    Constant time is the ceiling every other class is measured against.
    """
    return values[0]

Linear search is the honest one-pass cost. It looks at elements until it finds what it wants; in the worst case it looks at all of them. The optional probe list records every index it touches, which is what feeds the animation later:

def linear_search(values, target, probe=None):
    """O(n): scan left to right until the target is found.

    Returns the index of `target`, or -1. Every index it examines is appended to
    `probe` (when given) so the search can be animated. Worst case — the target
    is last or absent — touches all n elements, so the work grows in step with n.
    """
    for i, value in enumerate(values):
        if probe is not None:
            probe.append(i)
        if value == target:
            return i
    return -1

Binary search is where the logarithm comes from, and it only works because the input is sorted. It keeps a window, looks at the middle, and throws away the half that can't contain the target. Halving n over and over is the definition of a logarithm:

def binary_search(values, target, probe=None):
    """O(log n): halve a SORTED range each step.

    Invariant: if `target` is present it lies in values[lo:hi]. Each iteration
    throws away half of what's left, so the number of steps is the number of
    times n can be halved before nothing remains — log2(n). Each probe records
    the live window (lo, hi, mid) so the animation can show the range collapsing.
    """
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append((lo, hi, mid))
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1      # target is in the right half
        else:
            hi = mid          # target is in the left half
    return -1

Merge sort is the $O(n \log n)$ workhorse and the concrete form of that recurrence from the last section — split, sort the halves, merge:

def merge_sort(values):
    """O(n log n): split in half, sort each half, merge the two sorted halves.

    The recurrence T(n) = 2T(n/2) + O(n) unfolds to O(n log n): there are log n
    levels of splitting, and the merges at each level together touch all n
    elements. This is the price of a comparison sort that never degrades.
    """
    if len(values) <= 1:
        return list(values)
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    return _merge(left, right)


def _merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

The nested loop is the shape to fear. Two loops over n means about $n^2/2$ comparisons, which quadruple every time the input doubles:

def count_pairs(values, threshold):
    """O(n^2): every element against every other — a nested loop.

    Counts unordered pairs whose sum exceeds `threshold`. The work is about
    n^2 / 2 comparisons, so when n doubles the cost quadruples. This is the class
    that quietly kills programs: fine on the test data, unusable in production.
    """
    n = len(values)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if values[i] + values[j] > threshold:
                count += 1
    return count

And the naive recursive Fibonacci is the cautionary tale — the reason a whole family of chapters later exists to kill this pattern. Every call makes two more, so the work doubles with each step up in n:

def fib_recursive(n):
    """O(2^n): the naive recursion recomputes the same subproblems endlessly.

    The cautionary tale. Each call spawns two more, so the number of calls
    roughly doubles with every increment of n. Painless at n=25, hopeless at
    n=50. The dynamic-programming chapters exist to fix exactly this.
    """
    if n < 2:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

That last one is not academic. Timing it once, fib_recursive(30) took about 51.56 ms on the machine that generated this page — for a single number. Push it to 45 and you're waiting minutes; to 60, longer than you'll be alive. Same answer, catastrophic shape.

Watch it work

This is the whole chapter in one picture. Both searches are hunting the same target in the same 24-element sorted array. The top row is the linear scan, the bottom row is binary search. Orange is the cell being examined right now, faded cells have been ruled out, blue is the range binary search still has to consider, and green is the hit.

Step through it. Watch the linear scan crawl one cell at a time from the left while binary search leaps to the middle and throws away half the array at every move. For this target the scan needs 20 probes; binary search needs 5. That gap is the difference between $O(n)$ and $O(\log n)$, and it only grows: at a million elements the scan needs a million probes and binary search needs twenty.

The complete code

Here's the whole thing, both versions in one place — flip between them. The from-scratch tab is the six functions assembled; the library tab is what you'd actually write, because Python ships all three: bisect for the binary search, sorted for the sort, list.index for the linear scan. Each built-in is the same Big-O as ours — just implemented in C.

"""From-scratch reference functions spanning the core complexity classes.

Each function does honest work and can optionally record the operations it
performs (into a `probe` list) so the chapter can animate it. With `probe=None`
the functions run clean, at their natural cost — that's what gets timed. The
point of this chapter is not any one function; it is the SHAPE of the cost as
the input grows, so we keep one small representative of each growth class.
"""


# region: constant_time
def first(values):
    """O(1): touch one element, no matter how long the list is.

    A million elements or ten, this does the same single indexing operation.
    Constant time is the ceiling every other class is measured against.
    """
    return values[0]
# endregion


# region: linear_search
def linear_search(values, target, probe=None):
    """O(n): scan left to right until the target is found.

    Returns the index of `target`, or -1. Every index it examines is appended to
    `probe` (when given) so the search can be animated. Worst case — the target
    is last or absent — touches all n elements, so the work grows in step with n.
    """
    for i, value in enumerate(values):
        if probe is not None:
            probe.append(i)
        if value == target:
            return i
    return -1
# endregion


# region: binary_search
def binary_search(values, target, probe=None):
    """O(log n): halve a SORTED range each step.

    Invariant: if `target` is present it lies in values[lo:hi]. Each iteration
    throws away half of what's left, so the number of steps is the number of
    times n can be halved before nothing remains — log2(n). Each probe records
    the live window (lo, hi, mid) so the animation can show the range collapsing.
    """
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if probe is not None:
            probe.append((lo, hi, mid))
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1      # target is in the right half
        else:
            hi = mid          # target is in the left half
    return -1
# endregion


# region: merge_sort
def merge_sort(values):
    """O(n log n): split in half, sort each half, merge the two sorted halves.

    The recurrence T(n) = 2T(n/2) + O(n) unfolds to O(n log n): there are log n
    levels of splitting, and the merges at each level together touch all n
    elements. This is the price of a comparison sort that never degrades.
    """
    if len(values) <= 1:
        return list(values)
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    return _merge(left, right)


def _merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged
# endregion


# region: count_pairs
def count_pairs(values, threshold):
    """O(n^2): every element against every other — a nested loop.

    Counts unordered pairs whose sum exceeds `threshold`. The work is about
    n^2 / 2 comparisons, so when n doubles the cost quadruples. This is the class
    that quietly kills programs: fine on the test data, unusable in production.
    """
    n = len(values)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if values[i] + values[j] > threshold:
                count += 1
    return count
# endregion


# region: fib_recursive
def fib_recursive(n):
    """O(2^n): the naive recursion recomputes the same subproblems endlessly.

    The cautionary tale. Each call spawns two more, so the number of calls
    roughly doubles with every increment of n. Painless at n=25, hopeless at
    n=50. The dynamic-programming chapters exist to fix exactly this.
    """
    if n < 2:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)
# endregion

"""The tools a working Python programmer actually reaches for.

The lesson of this chapter's face-off: the library changes the CONSTANT FACTOR,
not the growth class. `bisect` is still O(log n); `sorted` is still O(n log n).
They win because they run in C, not because they bend the asymptotics — the
curve has the same shape, just a gentler slope.
"""
import bisect


# region: linear_builtin
def linear_search_builtin(values, target):
    """O(n): list.index scans left to right, same as the from-scratch loop —
    but the scan runs in C, so the constant is far smaller."""
    try:
        return values.index(target)
    except ValueError:
        return -1
# endregion


# region: binary_builtin
def binary_search_builtin(values, target):
    """O(log n): the standard library's bisect does the halving in C. Returns
    the index of `target`, or -1 if absent, to match the from-scratch signature."""
    i = bisect.bisect_left(values, target)
    if i < len(values) and values[i] == target:
        return i
    return -1
# endregion


# region: sort_builtin
def sort_builtin(values):
    """O(n log n): Timsort. Same asymptotic class as merge sort, but adaptive
    (it exploits runs that are already ordered) and implemented in C."""
    return sorted(values)
# endregion

Scratch vs library

Here's the face-off, and it makes the chapter's central point better than any paragraph. The chart times the from-scratch code against the built-in for the linear search, the binary search, and the sort, across input sizes up to 16000. Each pair of lines has the same shape — because they're the same complexity class — with the library's line sitting lower, because it runs in C:

At n = 16000 the built-in sort finished in about 1.28 ms against merge sort's 15.6 ms — roughly twelve times faster. The built-in searches beat ours by about five or six times. Notice what did not happen: the library did not turn a linear search into a logarithmic one, or a quadratic sort into a linearithmic one. It made the same-shaped curve cheaper by a constant factor. That is the whole relationship between Big-O and real performance. Big-O picks the algorithm; the constant — the language, the implementation, the cache behavior — decides how far under the curve you land.

Where you'll actually meet it

Complexity analysis is not a classroom exercise you leave behind; it's the vocabulary of every technical decision that involves data at scale. It's the reason a database uses a B-tree index instead of scanning every row — $O(\log n)$ lookups instead of $O(n)$. It's why a senior engineer flags the innocent nested loop in code review: that $O(n^2)$ is fine on the hundred rows in the test fixture and a fire on the million rows in production. It's the first thing a technical interview probes, because it separates people who can reason about scale from people who can only run code and hope. And it's the label on every chapter that follows: each data structure in this book is really a trade — spend some memory or some setup time to move an operation from $O(n)$ down to $O(\log n)$ or $O(1)$.

Takeaways

Big-O is a way to talk about how work grows with input size, with the constants thrown away on purpose so that what's left is a property of the algorithm and not of your hardware. Learn to read the ladder — $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$ — and to spot which rung a piece of code sits on, usually by counting nested loops and asking whether each step throws away a constant fraction of the work.

Use it as a filter, not a verdict. It rules out the algorithms that won't scale and tells you where to spend effort; then you measure to choose among what's left, because the constants it hides are sometimes the ones that pay your bills. Every remaining chapter is a concrete instance of this trade — a structure that buys a better exponent on some operation you care about. From here on, when we build something and race it against the library, the question is always the same two-parter: what's the Big-O, and what's the constant. This chapter is how you answer the first. The rest of the book is how you earn the second.