Card 08/ 08
Recap: Big O Notation
Keep the largest term, drop the constant, name the case, and estimate before you code.
Big O Notation comes down to the six ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| Big O counts steps as a function of n and keeps only how the count grows, not seconds | Big O Notation: How Cost Grows With Input |
| Keep the fastest-growing term, then drop its constant factor | Big O Example: Simplifying 3n² + 5n + 2 |
| Six classes, ranked by what doubling n does to each | The Common Growth Classes |
| Steps divided by about 10⁸ a second give an order-of-magnitude time | Estimate Whether an Algorithm Finishes in Time |
| A case picks the cost function; O, Ω and Θ bound it | Bounds and Cases Are Different Questions |
| A bare O(1) may be an expected case; name the case | Reading Big O as the Worst Case |
Keep the six growth classes at hand, with the doubling test that tells them apart.
| Class | Doubling n does |
|---|---|
| O(1) | Nothing |
| O(log n) | Adds one step |
| O(n) | Doubles it |
| O(n log n) | A little more than doubles it |
| O(n²) | Multiplies it by four |
| O(2ⁿ) | Squares it |
Together they let you read a cost, compare it with another, and say before running anything whether a program will cope with its input.
← → move through sections and cards