Big-O Notation

Big-O answers one question: when the input grows, how fast does the work grow? It deliberately throws away everything else. The machine, the language and the constant cost of each step all change a number, while growth changes whether the program finishes at all. Lantern's scan of 2 million records and its index lookup differ by more than any hardware upgrade could close, and Big-O is the compact way to say so.

It is also the shared vocabulary of the whole field. Interviews ask for it because every engineer can check it. Production needs it for a better reason: it predicts what happens to a service when its data grows tenfold, which is the question behind nearly every capacity outage.

Growth, Not Speed

Big-O classifies a procedure by the shape of its cost curve, not by its speed. O(n), read "order n", means that doubling the input roughly doubles the work. O(n²) means that doubling the input quadruples it. O(1) means the work does not grow with the input at all. None of these says how many milliseconds anything takes.

The chart below plots three classes over the same inputs. At n equal to 10 they are close enough to argue about. By n equal to 32 the quadratic curve has left the chart at 1,000 steps, while n log n is near 160 and n is at 32. By 100, n log n has reached about 660 and n has reached 100. The curves never cross back.

Dropping Constants and Lower Terms

Suppose a scan costs three steps per record plus five steps of setup: 3n + 5. The five disappears at any real size. The three depends on what counts as a step and how fast the machine does one, so it changes from one computer to the next. Big-O drops both and calls the scan O(n).

The same rule removes smaller terms. A procedure that costs n² + 1,000n steps is O(n²), because at a million items the second term is a tenth of one percent of the total. What is left after the dropping is the one fact that holds on every machine: how the work grows.

Reading Code for Its Class

Four rules cover most code. Statements in sequence add, and the biggest term wins. A loop multiplies its body's cost by the number of times it runs. Two nested loops over the same input give n². A loop that halves what is left each time runs about log n times: 2 million halves down to one in 21 steps, and a billion in 30.

def first(records):                 # O(1): one step whatever n is
    return records[0]

def letters_used(records):          # O(n): the inner loop is fixed at 26
    for r in records:
        for letter in "abcdefghijklmnopqrstuvwxyz":
            ...

def duplicate_pairs(records):       # O(n²): every record against every record
    for a in records:
        for b in records:
            ...

The three functions above make the trap visible. The first reads one element and is O(1) no matter how long the list is. The second has two nested loops but is O(n), because the inner loop always runs 26 times: its trip count is fixed, not tied to the input. The third also has two nested loops, and this time both run over the records, so it is O(n²). The indentation of the second and third is identical. The trip counts decide the class.

Lantern's Two Searches in Big-O

The scan is O(n) in the size of the catalogue. The index lookup is O(1) to find the term, on average, plus O(k) to read its k matching records, and neither part depends on the 2 million. Grow the catalogue tenfold to 20 million and the scan costs ten times more. The lookup for a given query costs about the same, because the number of records matching a rare surname hardly changes.

That one sentence makes the case for building an index, and it is the pattern behind every index in every database: pay once, when the data is written, so that every read stops paying in proportion to the data.

Upper Bounds, Lower Bounds, Tight Bounds

Strictly, O is a ceiling: "grows no faster than". Its partner Ω, omega, is a floor: "grows at least as fast as". Θ, theta, is both at once: "grows exactly like". By the strict reading, saying binary search is O(n) is true, because log n grows no faster than n, and it is also useless.

Working engineers write O and mean the tight bound, the smallest honest ceiling. This book does the same from here on. When a page says a hash lookup is O(1), it means the lookup does not grow with the table, not merely that it grows no faster than something larger.

What Big-O Does Not Tell You

Big-O says nothing about constants, nothing about small inputs, nothing about memory, and nothing about which case was analysed. An O(n log n) sort loses to O(n²) insertion sort on a dozen items; real sort functions switch to insertion sort for short runs. An O(n) scan of a short array beats an O(log n) tree because of how processor caches work, which is the subject of Chapter 4. And "hash lookup is O(1)" is a statement about the average, which an attacker can turn into O(n).

So Big-O is the first question, not the last. It picks the design that survives growth. A benchmark then picks between implementations of the same class, and checks that the analysis was right.