Big-O & Complexity
Tunebox starts with the 40 songs on your laptop. A year later it holds 40 million. Some features will feel exactly as fast as they did on day one; others will go from instant to unusable — and nobody touched the code. Big-O is how you tell which is which before your users do.
Count steps, not seconds
A stopwatch measures your laptop, your Python version and whatever else was running. What you want is a property of the code: how many basic steps it takes for an input of size n, and how that number grows as n grows.
Double the library and the unlucky searches double too. That's linear growth, written O(n). Now put a loop inside a loop:
steps = 0
for i in range(4):
for j in range(4):
steps += 1
print(steps)The growth classes you'll meet
Nearly everything in this course lands in one of six classes. From gentle to brutal, each with the Tunebox feature that has it:
| Big-O | name | Tunebox example |
|---|---|---|
| O(1) | constant | look up a song by id in a dict |
| O(log n) | logarithmic | binary search a sorted list of titles |
| O(n) | linear | scan every song for a title |
| O(n log n) | linearithmic | sort the library by play count |
| O(n²) | quadratic | compare every pair of songs for duplicates |
| O(2ⁿ) | exponential | try every subset of songs to fill exactly 60 minutes |
Same library sizes, very different step counts:
From a thousand songs to a million, a scan does 1,000× the work, a sort about 2,000×, and the all-pairs duplicate check a million times more. Binary search goes from 10 steps to 20.
❓ Cross-question — "Why
n.bit_length()for log n?" It's the number of times you can halvenbefore reaching zero — exactly what binary search does, discarding half the list per step. The base of the log never matters in Big-O: log₂ n and log₁₀ n differ only by a constant factor.
Step through the halving and watch n collapse:
Drop the constants and the small stuff
Big-O describes the shape of growth, so two simplifications are always allowed:
- Drop constant factors.
2nand500nare both O(n) — double n, double the work. - Keep only the biggest term.
3n² + 5n + 100is O(n²). At n = 1,000 the n² term is 3,000,000 and the rest is 5,100 — a rounding error.
Loops one after another add; loops inside each other multiply.
def work(n):
steps = 0
for i in range(n):
steps += 1
for i in range(n):
steps += 1
return steps
print(work(10), work(20))Watch out: a smaller Big-O isn't automatically faster for your data. Scanning 8 songs beats building a dict of those 8 songs to look one up. Big-O says who wins as n grows — not who wins at n = 8.
Best, worst and average case
find_scan took 1 step when the song was first and n when it was last or
missing. Same code, different inputs:
- best case — the kindest input: 1 step.
- worst case — the cruellest input: n steps.
- average case — over every position, about n / 2 steps. Still O(n).
A bare "scanning is O(n)" means the worst case — the promise you can make to every user, not just the lucky ones. Here's the classic all-pairs duplicate check, which is O(n²) in its worst case (no duplicates at all). It's also broken:
Three different songs should print False. It prints True — find the comparison that can never be False.
Time vs space
Complexity has a second axis: how much extra memory an algorithm needs as n grows. The nested-loop check uses O(1) extra space and O(n²) time. A set flips the trade:
Spending memory to save time is the most common trade in this course. You'll make it in almost every lesson.
Amortized cost — why append is O(1)
A Python list keeps spare slots at the end. append drops the item into a spare
slot: O(1). When the spares run out, the list moves to a bigger block and copies every
item across — O(n) for that one call.
So is append O(n)? Judge the whole sequence. Say capacity doubles each time: n
appends trigger copies of 1 + 2 + 4 + … items, which sums to less than 2n. Spread over
n appends, that's a constant per append — amortized O(1). The expensive call is
rare enough to pay for itself.
Byte counts differ between platforms (CPython grows by roughly an eighth, not double); the rhythm doesn't — long quiet stretches between resizes.
Amortized isn't average case. Average case averages over different inputs. Amortized averages over a sequence of operations on one structure, and it's a guarantee: no lucky input required.
The real cost of everyday Python
Knowing what the built-ins cost is most of practical complexity:
| operation | cost | why |
|---|---|---|
songs[i], len(songs) |
O(1) | jump straight to the slot; length is stored |
songs.append(x) |
O(1) amortized | spare slots at the end |
songs.pop() |
O(1) | removes the last item, nothing moves |
songs.pop(0), songs.insert(0, x) |
O(n) | every other item shifts one slot |
x in songs |
O(n) | compares against each item in turn |
x in song_set, song_dict[key] |
O(1) average | hash straight to the right bucket |
songs[a:b] |
O(b − a) | a slice is a copy |
sorted(songs) |
O(n log n) | a comparison sort |
You can watch in work by counting comparisons:
pop(0) hides the same kind of cost:
queue = ["a", "b", "c", "d", "e"]
moves = 0
while queue:
moves += len(queue) - 1 # pop(0) shifts everything behind the front
queue.pop(0)
print(moves)Coming from Java/JS: the traps are identical. JS
shift()/unshift()and JavaArrayList.remove(0)/add(0, x)are O(n);array.includes(x)andlist.contains(x)scan;Set.hasandHashSet.containsare O(1) on average.
❓ Cross-question — "So should I never use
pop(0)?" On a 20-song queue, write whatever reads best. In a loop draining a million plays, usecollections.deque, whosepopleft()is O(1). Queues get a lesson of their own in the next section.
Idioms & real-world patterns
Find the line that makes it slow
Cost is decided by the most expensive operation inside the most loops. When a function
is slow, look for an O(n) call hiding inside a loop — in on a list, pop(0),
.index(), .count(), a slice. Each one quietly turns O(n) into O(n²):
⚡ Advanced — Big-O, Big-Ω and Big-Θ
Formally, Big-O is an upper bound: f(n) is O(g(n)) if, beyond some n, f(n) ≤ c·g(n) for a fixed constant c. That makes a scan technically O(n²) too — true, and useless. Two partners complete the picture:
- Big-Ω (omega) — a lower bound: the cost grows at least this fast.
- Big-Θ (theta) — a tight bound: O and Ω at once. A scan's worst case is Θ(n).
In code review, "O(n)" almost always means "Θ(n) in the worst case". Ω earns its keep when you claim something can't be done faster: finding a song in an unsorted list is Ω(n) in the worst case, because any song you skip might have been the one.
⚡ Advanced — watching O(2ⁿ) explode
Each song is either in a mix or out of it, so n songs have 2ⁿ possible mixes:
One more song doubles the work. That's why these problems get their own techniques later — backtracking prunes the search, dynamic programming stops repeating it.
🎯 Your turn
Build the scale planner: steps_to_find(n, method) returns the worst-case steps to
find one song among n:
"scan"checks every song →n"binary"halves a sorted list →n.bit_length()"index"is one hash lookup →1
For example steps_to_find(1000, "binary") → 10, and steps_to_find(1000, "scan") → 1000.
Hint — three methods, three ifs. Notice which answer never mentions n.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅