Big O Notation: How Cost Grows With Input

Big O notation describes how the work an operation does grows as its input grows. It counts steps, not seconds, and keeps only the part that decides the growth. This card covers what is counted, why the rest is dropped, and what Big O cannot tell you.

A sign-up list holds 2,000,000 names, and you want to know whether any name appears twice. One method compares every pair of names; another reads them once, checking each against a set of names already seen.

At about 10⁸ simple steps a second, a rough rate for one processor core, the first method takes about five and a half hours and the second 0.02 seconds. What separates them is how their work grows.

Big O compares methods without a stopwatch. Write each cost as a count of simple steps as a function of the input size, n: every pair costs n(n − 1)/2 steps, one pass about n. Keep only how each count grows as n grows large, and the pair method is O(n²), read "order n squared", while the one-pass method is O(n).

A taxi fare works the same way: on a long ride the distance decides the bill, not the fixed charge to get in. The picture breaks on exactness: a fare is an exact sum, while Big O keeps only the shape of the growth.

So Big O describes a cost by its fastest-growing part, without constant multipliers: costs that differ only by a constant factor share a Big O.

In the table below, log n is roughly how many times n can be halved before it reaches 1.

Each row is one input size.

A smaller Big O does not make a method faster at every size. At n = 50, a cost of 100n steps, which is O(n), comes to 5,000, while n², which is O(n²), comes to 2,500. Beyond n = 100 the O(n) cost is always the smaller. Big O says which method wins once n is large enough.

Every data structure in this subject is compared by the Big O of its operations, which lets you choose between them before writing any code.