Lesson 17 · Algorithms

How fast is fast? Big O

Timing code with a stopwatch tells you about one computer on one day. Big O asks a better question: how does the number of steps grow as the input grows? Watch five growth rates race as n steps up from 10 to a million, from the O(1) bar that never moves to the O(n²) bar that reaches a trillion.

11 min11 steps5 questionsIntermediate

Fig 17 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01A function looks at every item in a list once. The list grows from 1,000 items to 1,000,000. Roughly how many more steps does it take?

Looking at each item once is O(n): the steps grow at the same rate as n. n grew 1,000 times, so the steps grow about 1,000 times.

02Binary search (like bisect) halves a sorted list each step. About how many steps does it need for 1,000,000 items?

It is O(log n). Halving a million again and again reaches 1 after about 20 halvings, because 2 to the power 20 is about a million.

03A piece of code takes 3n² + 5n + 2 steps. What is its Big O?

Big O keeps only the fastest-growing term and drops constant factors: the 5n and the 2 become tiny next to n², and the 3 is dropped. So it is O(n²).

04Which of these Python operations is O(n) for a list of n items?

Inserting at the front shifts every item one place along, so it takes about n steps. Indexing, dict lookup (on average) and len() each take about the same time at any size.

05x in items finds x at the very first position. Why is it still called O(n)?

The best case is 1 check, but in the worst case it checks all n items. Big O usually promises a limit for the worst case, so it is O(n).

Key terms

Glossary

Step: One simple action a program does, such as reading one item or comparing two numbers. Big O counts steps instead of seconds.
n: The size of the input: how many items the code works on.
Big O: A way to describe how the number of steps grows as n grows, keeping only the fastest-growing part and ignoring constant factors.
Constant time, O(1): The step count stays the same however big n gets, as in items[5].
Logarithmic, O(log n): The steps grow by one each time n doubles, as in binary search: about 20 steps for a million items.
Linear, O(n): The steps grow at the same rate as n, as in checking every item once.
Quadratic, O(n²): The steps grow with n times n, as in a loop inside a loop over the same items.
Worst case: The input that makes the code take the most steps. Big O usually describes this case.
Average case: The typical step count over many inputs. A Python dict lookup is O(1) on average but O(n) in the rare worst case.
O(n log n): About n times log n steps, as in sorted(): a little more than linear, far less than quadratic.
Space complexity: How the extra memory a piece of code needs grows with n. sorted() builds a new list, so it uses O(n) extra space.

Fine print

Notes and sources

The O(log n) bar counts the most halvings binary search can need on n items, which is log₂(n + 1) rounded up: 4 for 10 items, 10 for 1,000 and 20 for 1,000,000. bisect comes from the standard library: from bisect import bisect.
The O(n log n) bar shows n × log₂ n. Python's own sort is guaranteed to finish within a constant times n log n comparisons, even in the worst case.
The bars stand against a log scale: each line on the back wall is 10 times the one below it. On an ordinary scale the trillion bar would be a million times taller than the million bar.
At one step per nanosecond (a billionth of a second), 10¹² steps take 1,000 seconds, about 17 minutes, while 2 × 10⁷ steps take 0.02 seconds. Real steps take different times; Big O ignores that on purpose.
A dict lookup is O(1) on average because a dict is a hash table. In rare worst cases, when many keys land in the same slot, it can take up to O(n).
If x is in the list at a random position, x in items makes (n + 1) / 2 checks on average, about 500,000 for a million items.

Quiz Unlocks after the last step.