Big-O Notation

Comparing growth rates

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Big-O describes how running time grows: $\log n < n < n\log n < n^2 < 2^n$.
• For $O(n^2)$, 10× the data means about 100× the time.
• Greedy algorithms are fast, but don’t always find the best answer.

Steps

1. How work grows
2. Ten times the data
3. Constants matter… for a while
4. Exponential time
5. Sorting a million
6. Greedy change