Big-O Notation in Plain English

Big-O notation is shorthand for one question: as your input gets bigger, how fast does the work get bigger? It is not a stopwatch. It is a description of shape — the curve your runtime traces as n climbs toward infinity.

What Big-O Actually Measures

When people write O(n), the n is the size of the input — the number of items in a list, characters in a string, rows in a table. Big-O describes the growth rate of some cost (usually running time, sometimes memory) as a function of that n.

The crucial move is that Big-O throws away two things on purpose: constant factors and lower-order terms. A function that does 3n + 50 steps is just O(n). One that does n^2 + 100n + 9 is O(n^2). The reasoning is that as n grows large, the dominant term swamps everything else — at n = 1,000,000, the n^2 part dwarfs the 100n part so completely that the smaller terms are noise.

This is why Big-O is called asymptotic analysis: it cares about behavior as n heads toward the large end, not the exact step count at small n. That abstraction is the source of both its power and its limits.

The Classes You Will Actually Meet

A handful of growth classes cover most code you read. From best to worst:

• O(1) — constant. The work doesn’t depend on n at all. Looking up a value in a hash map by key, or reading array[5], takes the same time whether the structure holds 10 items or 10 million.
• O(log n) — logarithmic. Each step throws away a large fraction of the remaining input. Binary search on a sorted array is the classic case: 1,000,000 items take about 20 comparisons, because each comparison halves the search space. Doubling the input adds just one step.
• O(n) — linear. You touch each item a constant number of times. Scanning a list to find a maximum, or summing every element, grows in lockstep with the input.
• O(n log n) — linearithmic. The realistic floor for general-purpose comparison sorting. Merge sort and heapsort live here, and well-tuned quicksort hits it on average. Slightly worse than linear, but for most data it feels nearly as fast.
• O(n^2) — quadratic. Two nested loops over the same data. Comparing every pair of items, or naive bubble sort. Fine for 100 items, painful at 10,000, hopeless at 10,000,000.
• O(2^n) — exponential. Each added element roughly doubles the work. Brute-forcing every subset of a set, or naive recursive solutions to certain combinatorial problems. Adding one item to the input can double your runtime, so these melt down past a few dozen elements.

A quick way to spot quadratic code in the wild:

# O(n^2): for each item, scan all items again
for a in items:
    for b in items:
        if a is not b and collides(a, b):
            ...

If you find yourself nesting a loop over the same collection, ask whether a hash set or a sort could turn that O(n^2) into O(n) or O(n log n).

Why a “Worse” Big-O Can Still Win

Because Big-O hides constants, two algorithms in the same class — or even different classes — can swap places on small inputs. Insertion sort is O(n^2), and quicksort is O(n log n), yet on tiny arrays insertion sort is often faster in practice, since its per-step constant is small and it has no recursion overhead. This is exactly why many real-world sort implementations switch to insertion sort for small subarrays.

The lesson: Big-O tells you who wins eventually, as n grows. For a list of 8 elements, the constant factors and cache behavior may matter far more than the asymptotic class.

How to Use It Day to Day

You rarely need to derive Big-O formally. The practical skill is pattern recognition: a single pass is linear, halving each step is logarithmic, nested passes over the same data are quadratic, and “try every combination” is usually exponential. When something is slow, identifying the class tells you whether to optimize the constant (micro-tuning, caching) or change the algorithm entirely (a better class). Dropping from O(n^2) to O(n log n) on a million-row job is the difference between minutes and milliseconds — and that is the kind of win no amount of micro-tuning inside a quadratic loop can match.