Big O: How the Bars Grow

Lesson 5 of 11 · 7 min · Free, no account needed

What you will learn

Big O names how the step count grows with n: O(1), O(log n), O(n), O(n²).
Doubling n: O(1) stays, O(log n) adds one, O(n) doubles, O(n²) grows 4 times.
Constants and small terms are dropped: 100n is still O(n), and for big n it beats n².

Two apps feel instant with 100 users. With a million, one still works. Which?
Start with the pairs program from lesson 1.
Four kinds of growth. Double n and watch the bars.
The chart zooms out to fit the tallest bar. Go all the way to 1024.
Now race them in real time.
A million steps a second. Pick n, press Run. Try the biggest n last.
Big O.
Big O names the growth of a program's step count as n grows. It ignores the exact numbers and keeps the shape.
O(1): the same work for any n. O(log n): halving, like binary search. O(n): one loop. O(n²): a loop inside a loop.
Constants are dropped: 3n + 5 steps is O(n). For big enough n, the shape always wins.
Sort the code by growth.
a is a list of n items.
Your app is clunky: c steps for every user. The rival does n x n.
Pick your c. Then find the number of users where the rival gets slower.
c x n = n x n exactly when n = c. For every n bigger than c, n x n is bigger, and the gap keeps growing. That's why constants are dropped in Big O.
Draw y = x² on the graph.
Drag the three points. The blue curve is y = log₂ x.
Squaring: 2 x 2 = 4, 4 x 4 = 16, 6 x 6 = 36. Each time x goes up by 2, y climbs more than the time before.
An O(n²) program takes 1 second on 1000 items. About how long on 10 000?
Steps grow like n². (10n)² = 100 n², so the time grows 100 times: 1 s becomes 100 s.
Speed round: pick the racer.
A size and a time limit. Tap the slowest class that still finishes. The last round is your app.

Lessons are interactive and need JavaScript. Turn it on to play them.