🧠 Algorithms & Problem Solving, lesson 5 of 6
Big-O intuition
Predict how an algorithm slows down as data grows, by counting steps.
10 min
1 exercise
2 quizzes
0/3 solved
Getting Python ready… examples can run in a moment.
Big-O notation describes how the work grows as the input grows. Ignore small details and ask: if the input doubles, what happens to the work?
- O(1): constant, e.g.
d[key],xs[0] - O(log n): doubling adds one step (binary search)
- O(n): doubling doubles the work (one loop)
- O(n log n): good sorts like merge sort and
sorted() - O(n²): doubling quadruples the work (a loop inside a loop)
Counting operations
Each time n doubles: linear doubles, quadratic
grows 4×, and log grows by just 1.
A function loops over n items, and inside that loop it loops over all n items again. If n goes from 1,000 to 2,000, the work roughly...
What does this print?
Race: bubble sort vs merge sort
Going from 100 to 1,000 items costs bubble sort 100× more comparisons (O(n²)), but merge sort only about 16× more (O(n log n)).
Hidden loops. Some one-liners secretly loop over
a whole list: x in my_list, .index(),
.remove(), .count(), insert(0, x) and
pop(0) are all O(n).
Sets and dicts use hashing instead, so x in my_set
and d[key] are O(1) on average. A list membership
test inside a loop quietly turns O(n) code into O(n²).
list vs set: counting comparisons
The list compares against every item until it hits
999; the set jumps straight to the right spot using
the hash. Try Key(0) as the target.
From O(n²) to O(n)
has_duplicates works, but compares every pair of
items (O(n²)). Rewrite it to walk the list once,
remembering what you've seen in a set. The check
counts comparisons, so the nested loops won't pass.