What is Big O notation? How fast algorithms grow

Big O notation is a way of describing how the work an algorithm does grows as its input gets bigger. Instead of timing a program in seconds, which depends on the computer, it counts steps as a function of the input size, n, and keeps only the part that grows fastest. Saying a method is O(n²) means that doubling the input roughly quadruples the work, on any machine.

In short

• Big O describes growth, not speed: how the step count rises as the input rises, with constant factors dropped.
• The common classes, from best to worst, are O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ), and the gaps between them become enormous for large inputs.
• Strictly, Big O is an upper bound: an O(n) method never needs more than a fixed multiple of n steps, once n is large enough.

What does Big O actually measure?

It measures the shape of growth. Suppose a program checks a guest list for a name by reading names one by one. With 100 guests it might read up to 100; with 1,000, up to 1,000. However fast the computer, the work rises in step with the list, and that relationship is what O(n) names. The letter O stands for "order", as in order of growth.

Two rules turn a precise step count into Big O. Drop constant multipliers, and keep only the fastest-growing term. An algorithm that takes 3n² + 5n + 100 steps is O(n²), because at n = 1,000 the 3n² part is 3,000,000 of the 3,005,100 steps, 99.8% of the work, and its share only rises from there. The 3 is dropped too, because it depends on details such as the language and the chip, while the n² does not.

Formally, as the US National Institute of Standards and Technology's Dictionary of Algorithms and Data Structures puts it, f(n) = O(g(n)) means there are fixed positive numbers c and k such that f(n) is at most c × g(n) for every n of at least k. Here f(n) is the real step count, g(n) is the simple shape it is compared with, c absorbs the constant factors, and k says "for large enough inputs". The notation comes from number theory: the German mathematician Paul Bachmann introduced it in 1894, and computer science adopted it, along with companion symbols that Donald Knuth set out in a 1976 paper.

How different are the common classes?

The gaps look small on paper and are vast in practice. This table counts steps for each class at three input sizes; the last column assumes a computer doing 1 billion simple steps a second.

Class	Name	n = 10	n = 1,000	n = 1,000,000	Time at n = 1,000,000
O(1)	Constant	1	1	1	A billionth of a second
O(log n)	Logarithmic	about 3	about 10	about 20	20 billionths of a second
O(n)	Linear	10	1,000	1,000,000	A thousandth of a second
O(n log n)	Linearithmic	about 33	about 10,000	about 20 million	A fiftieth of a second
O(n²)	Quadratic	100	1,000,000	1 trillion	About 17 minutes
O(2ⁿ)	Exponential	1,024	a 302-digit number	a 301,030-digit number	Far longer than the age of the universe

At 10 items every class is fast; at a million, the choice of class matters more than any hardware. NIST's dictionary makes the same point with sorting: to sort 1,000,000 numbers, a typical O(n log n) method such as quicksort takes about 20 million steps on average, while the O(n²) bubble sort takes about a trillion, so a small desktop running the first can beat a supercomputer running the second. The exponential row is why some problems, discussed in P vs NP, are considered out of reach for large inputs: even at n = 100, 2ⁿ is about 10³⁰ steps, which at a billion a second is tens of trillions of years.

Why is binary search O(log n)?

Binary search finds an item in a sorted list by halving it. Look at the middle entry. If the target comes before it, throw away the back half; if after, the front half. Repeat on what's left.

Follow it on 1,000,000 sorted names. After one look, at most 500,000 remain; after two, 250,000; then 125,000, 62,500, 31,250 and so on. After 20 looks, at most one name is left, because 2 multiplied by itself 20 times is 1,048,576, just over a million. So the number of steps is the number of times n can be halved before reaching 1, which is the base-2 logarithm of n, written log₂ n. Double the list to 2 million names and binary search needs just one more look. That is what O(log n) means: each extra step doubles the size of the problem it can handle. It only works because the list is sorted, which is the kind of trade-off a data structure is chosen for.

Why are nested loops O(n²)?

Suppose you want to know whether any two guests on a list of n share a birthday, and you compare every guest with every other. The outer loop picks a guest; the inner loop compares them with everyone after them. For 1,000 guests that is 999 comparisons for the first, 998 for the second, down to 1, which adds up to 1,000 × 999 ÷ 2 = 499,500.

The exact count is n(n − 1)/2, or n²/2 − n/2. Drop the constant factor of one half and the smaller n term, and it is O(n²). The consequence is the useful part: 10 times as many guests means about 100 times as many comparisons, so 10,000 guests needs about 50 million. A better method sorts the list by birthday first, in O(n log n), and then checks only neighbors, in O(n), for O(n log n) in total. At 10,000 guests that is roughly 140,000 steps instead of 50 million.

What does Big O not tell you?

It doesn't tell you seconds. Two O(n) programs can differ tenfold in speed, because Big O hides constant factors on purpose. For small inputs a "worse" class can win: an O(n²) method with tiny constants beats an O(n log n) one with large constants on a list of 20 items, and real sorting libraries switch methods for short runs for that reason.

It doesn't, by itself, say which case it describes. Quicksort is O(n log n) on average and O(n²) in its worst case, and a fair description says which. Strictly, Big O is only an upper limit: a linear method is also, truthfully if unhelpfully, O(n²). Computer scientists use two companion symbols for precision, Ω (big omega) for a lower limit and Θ (big theta) for growth that is pinned from both sides, though everyday usage says "Big O" and means Θ.

And it ignores memory unless asked. The same notation measures space as well as time, and many choices trade one for the other: the memoized Fibonacci in recursion turns exponential time into linear time by storing every answer it has worked out.

Check yourself

• Without looking back, explain why doubling the input adds just one step to binary search, but quadruples the work of an O(n²) method.
• What two simplifications turn 3n² + 5n + 100 into O(n²), and why are they safe for large n?
• Name one thing Big O deliberately leaves out, and when that omission matters.

Sources

• Big-O notation — Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology
• Binary search — Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology
• Big O notation — Wikipedia
• Introduction to Algorithms, course 6.006 — MIT OpenCourseWare, 2020