Big O Notation study song
Quick answer
Big O notation describes how the running time or memory use of an algorithm grows as the input size n grows. It ignores constants and lower-order terms, so 3n^2 + 5n + 2 is simply O(n^2).
Exams ask you to rank growth rates, read a loop and state its complexity, and tell worst case from average case. The classic ladder runs from O(1) up through O(log n), O(n), O(n log n), O(n^2) and O(2^n). Because the whole topic is an ordered list, rhythm does a lot of the work. A chorus that repeats the ladder from slowest-growing to fastest-growing gives you the ranking on demand, and a verse can attach each class to one familiar algorithm.
5 facts to know about big o notation
- 1Big O gives an upper bound on growth rate, and constants and lower-order terms are dropped, so O(2n + 10) is O(n).
- 2Binary search on a sorted array runs in O(log n) because each comparison halves the remaining range.
- 3Merge sort runs in O(n log n) in the best, average and worst cases.
- 4Two nested loops that each run n times give O(n^2) time.
- 5Growth rates rank as O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).














