A handful of growth rates cover almost every algorithm in this course. Once you know them well, you can read a problem’s limits and know at once which rates can work.
The usual classes
From slowest growing to fastest growing:
| Class | Name | Example |
|---|---|---|
| 1 | constant | read a[i]; look up a key in a dict |
| log n | logarithmic | binary search |
| n | linear | one pass over a list |
| n log n | linearithmic | merge sort; sorted() |
| n² | quadratic | check every pair |
| n³ | cubic | check every triple; simple matrix multiply |
| 2ⁿ | exponential | try every subset |
| n! | factorial | try every order |
Each class eventually beats every class below it in the table, whatever the constants are. For example, 1,000 n is smaller than n² once n is more than 1,000.
What n can each class handle?
Step through the table. Each step picks a bigger n and shows how long each class would take.
| Class | Steps | Time | Against 10 seconds |
|---|---|---|---|
1 | |||
log n | |||
n | |||
n log n | |||
n² | |||
n³ | |||
2ⁿ | |||
n! |
Each row is a growth class. Each step picks a bigger size n. The time assumes about 10 million simple steps a second, which is roughly what plain Python manages. The bars compare each time with 10 seconds. 2ⁿ means n twos multiplied together, and n! means 1 × 2 × 3 × … × n.
This gives a useful habit. Read the limits first. Plain Python does roughly 10 million simple steps a second. So, for a few seconds of time:
- n up to about 10: n! may be fine.
- n up to about 20: 2ⁿ is fine.
- n up to about 300: n³ is fine.
- n up to about 3,000: n² is fine.
- n up to 1,000,000: you need n log n or better.
Where log n comes from
log₂ n is how many times you can halve n before you reach 1. Halve 1,000,000 twenty times and you reach 1, so log₂ 1,000,000 ≈ 20. That is why it grows so slowly: doubling n adds only 1.
A log appears whenever the work cuts the problem by a fixed fraction each step. Two common shapes:
while n > 1: # runs about log2(n) times
n = n // 2
i = 1
while i < n: # also about log2(n) times
i = i * 2
n log n usually means log n levels of work, with n steps at each level. Merge sort is the standard example, and lesson 5 shows why.
Exponential and factorial
2ⁿ doubles every time n grows by 1. It appears when each of n items is either in or out: a list of 30 items has 2³⁰, about a billion, subsets. n! (read “n factorial”, which is 1 × 2 × … × n) counts the orders of n items: 10 items have 3,628,800 orders, and 15 have over a trillion.
Now try BIGO-P1, Two loads that add up. The limits rule out checking every pair.
BIGO-3 counts as completed once you step through the figure to the last step.