Big-O & Data Structures
Big-O cheat sheet: growth rates from O(1) to O(n!), the cost of arrays, linked lists, hash tables, trees, heaps and tries, sorting algorithms compared, how to analyse an algorithm, and which data structure to reach for.
Cheat sheet · Offered as a template
In this diagram
- Big-O & Data Structures
- How running time grows with the size of the input, and what each common data structure costs.
- ① What Big-O says
- How cost grows as n grows, not how long it takes
- Drop constants and small terms: 3n² + 5n is O(n²)
- Usually the worst case, unless stated
- It applies to memory as well as time
- ② Growth, from best to worst
- O(1)
- constant hash lookup
- O(log n)
- logarithmic binary search
- O(n)
- linear one loop
- O(n log n)
- linearithmic merge sort
- O(n²)
- quadratic nested loops
- O(2ⁿ)
- exponential all subsets
- O(n!)
- factorial all orderings
- At n = 1,000,000: log n is about 20, n log n about 20 million, and n² a trillion.
- ③ Data structures
- ④ Pick a structure
- ⑤ Sorting
- ⑥ Spot it in code
- patterns.py
- ⑦ Analyse any algorithm
- Name the input size n
- Count the work in the innermost loop
- Multiply nested loops, add sequential ones
- For recursion, write the recurrence: T(n) = 2T(n/2) + n
- Keep only the fastest-growing term
- ⑧ Steps at n = 1,000,000
- log n
- n
- n log n
- n²
- A million steps feels instant. A trillion takes hours.
- ⑨ Words that trip people up
- Amortised: averaged over a run of operations (array append)
- Average case: over random inputs (quicksort)
- Worst case: the unlucky input
- O is an upper bound, Ω a lower bound, Θ both