Card 03/ 08
The Common Growth Classes
Constant, logarithmic, linear, n log n, quadratic and exponential, ranked from slowest-growing to fastest.
Most costs you will meet fall into one of six growth classes: constant, logarithmic, linear, n log n, quadratic and exponential. This card ranks them from slowest-growing to fastest, gives an everyday operation for each, and shows the test that tells them apart: double n and watch the cost.
You have a working program and a list of 1,000 items, and the list is about to double. Whether that matters depends on the growth class. A linear operation takes twice as long, a quadratic one four times as long. An exponential one squares its cost, which is the difference between a program that works and one that never finishes.
| Class | Name | Doubling n does | Example operation |
|---|---|---|---|
| O(1) | Constant | Nothing | Reading the item at a known position in an array |
| O(log n) | Logarithmic | Adds one step | Binary search, which halves a sorted list at each step |
| O(n) | Linear | Doubles it | Finding the largest value in an unsorted list |
| O(n log n) | Linearithmic | A little more than doubles it, 2.2 times at n = 1,000 | Sorting a list with Python's sorted |
| O(n²) | Quadratic | Multiplies it by four | Comparing every pair of items |
| O(2ⁿ) | Exponential | Squares it | Trying every on-off setting of n switches |
The doubling test works because each class is a different kind of formula. A constant does not mention n. A logarithm counts halvings: log n is the power you raise 2 to in order to get n, so log 1,000 is about 10, and doubling n adds one more halving. A linear cost is n times a constant. A quadratic cost is n times n, so doubling n doubles it twice. An exponential cost doubles for every extra item, so doubling n multiplies 2ⁿ by 2ⁿ again, which squares it.
Logarithms here are to base 2, but the base never matters in Big O. Changing it multiplies every logarithm by the same constant, and Big O drops constants.
So the six classes form a ladder. Each eventually outgrows every class before it, whatever constants either carries.
The six are common, not complete. O(n³), from three loops nested over the input, multiplies by eight when n doubles and sits between n² and 2ⁿ. O(n!), from trying every order of n items, grows faster than 2ⁿ. Any cost outside the six still slots into the ladder by the same doubling test.
Every cost stated in this subject is one of these classes, or one beside them. Each tells you how an operation will behave on a larger input before you run it.
← → move through sections and cards