How It Scales A song about Big O notation
Sing it back
Can you finish the lyrics?
Eight quick questions on “How It Scales”. No music, just your memory. Then share your score and challenge a friend.
Big O notation in one paragraph
Big O notation describes how an algorithm’s running time or memory use grows as the size of its input, n, grows, and it is most often used to state the worst case. It keeps only the fastest-growing term and drops constant factors, so an algorithm that takes 3n² + n + 5 steps is O(n²). Common classes, from slowest-growing to fastest-growing, are O(1) constant time, O(log n) such as binary search on a sorted list, O(n) such as linear search, O(n log n) such as merge sort, O(n²) such as nested loops or bubble sort, and O(2ⁿ) such as checking every subset of n items. Big O tells you how an algorithm scales, not its exact speed on a particular machine.
Key facts from the song
- Big O describes how running time or memory grows with input size n, most often in the worst case.
- Constants and lower-order terms are dropped: 3n² + n + 5 is O(n²).
- O(1) is constant time; O(log n) binary search halves a sorted list at every step.
- O(n) linear search checks items one by one; O(n log n) merge sort splits the list in halves and merges them back in order.
- O(n²) comes from nested loops such as bubble sort; O(2ⁿ) work doubles with every extra item, as in trying every subset.
Where it fits in your course
- US level
- College (undergraduate)
Lyrics
Verse 1
Big O describes how running time grows as the input size n climbs
It usually means the worst case, and it works for memory, not just time
Drop the constants, drop the smaller terms, just keep the biggest one
Three n squared plus n is big O of n squared, and we’re done
Chorus
Big O of one is constant time, the same at any size
Big O of log n, binary search, halve the sorted list each try
Big O of n is linear search, check each item down the line
Big O of n log n, merge sort: split in half, then recombine
Verse 2
Nested loops are n squared, double n and it’s four times the work
Bubble sort swaps neighbors pass by pass, that’s where those slow steps lurk
Two to the n: add one item and the work will double
Try every subset by brute force and you’re in exponential trouble
Chorus
Big O of one is constant time, the same at any size
Big O of log n, binary search, halve the sorted list each try
Big O of n is linear search, check each item down the line
Big O of n log n, merge sort: split in half, then recombine
Outro
Constant, log, linear, n log n, n squared, two to the n
Know how your code will scale before the input grows, my friend
Big O notation flashcards
Say the answer out loud, then tap the card to check it. Or test yourself quick-fire.
1What does Big O notation describe?
How an algorithm’s running time or memory grows as the input size n grows, usually in the worst case.
2What is 3n² + n + 5 in Big O notation?
O(n²): constants and lower-order terms are dropped.
3What is the time complexity of binary search, and why?
O(log n), because it halves the sorted list at every step.
4Which is O(n log n) and which is O(n²): merge sort or bubble sort?
Merge sort is O(n log n); bubble sort is O(n²).
Questions about Big O notation
Still wondering about something? Ask us and we’ll reply within two working days.
What is Big O notation in simple terms?
Big O notation is a way of describing how the time or memory an algorithm needs grows as its input gets bigger. It ignores constants and focuses on the overall growth rate, usually for the worst case.
Why is binary search O(log n)?
Each step of binary search halves the part of the sorted list still being searched. A list of n items can only be halved about log₂ n times before one item is left, so the number of steps grows logarithmically.
Why are constants dropped in Big O?
Big O describes how cost grows as n gets large, and for large n the fastest-growing term dominates. 3n² and n² both quadruple when n doubles, so both are O(n²).
What is the time complexity of bubble sort and merge sort?
Bubble sort is O(n²) in the worst case because it makes repeated passes comparing neighboring pairs. Merge sort is O(n log n) because it splits the list in half about log n times and does about n work merging at each level.