How It Scales A song about Big O notation

Subject
Computer science
Genre
Hip-hop
Level
College
Length
1:45
Tempo
96 BPM

More on this topic

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

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.

  1. 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.

  2. 2What is 3n² + n + 5 in Big O notation?

    O(n²): constants and lower-order terms are dropped.

  3. 3What is the time complexity of binary search, and why?

    O(log n), because it halves the sorted list at every step.

  4. 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.

Welcome to BrainBeats

Sign in or create your free account

No password needed. Pick Google, or we’ll email you a sign-in link.

Continue with Google

or

Part of BrainBeats Plus

Unlock this song

Start your free week

7 days free, then $5.99/month billed yearly. Cancel anytime.

or

Play a free song