Lesson 24 of 26 · about 17 min
How fast is my code?
Instead of timing code with a stopwatch, count how the number of steps grows as the input grows. That growth, written as Big-O, tells you whether code will still be fast with a million items.
🧭 What you need first: Floats and approximation
You lost your keys somewhere in a 10-room house. Checking every room one by one: at worst, 10 rooms. In a 100-room mansion: 100 rooms. The work grows in step with the house.
Now imagine a game: “I’m thinking of a number from 1 to 1,000.” If you guess 1, 2, 3…, it could take 1,000 tries. If each time I say “higher” or “lower” and you guess the middle, it never takes more than 10. Make it 1 to 1,000,000: still only 20.
Same problem, wildly different amounts of work. Computer scientists care less about “how many seconds” (that depends on the computer) and more about how the work grows when the problem gets bigger. That growth is written in Big-O notation.
Another way: handshakes
At a party, everyone shakes hands with everyone. 10 people: 45 handshakes. 100 people: 4,950. 10× the people, about 100× the handshakes. That’s O(n²) growth, and why “compare every pair” gets slow fast.
Another way: a phone book vs. a pile of business cards
Finding a name in a sorted phone book: open the middle, halve, halve… O(log n). Finding it in an unsorted shoebox of cards: look at every card, O(n). Sorting the cards once makes every future search fast.
Race two sorting methods
Both lanes sort the same 16 numbers. Each tick is one comparison. Then look at the table: what happens with 1,000 items?
Selection sort
0 comparisons
Merge sort
0 comparisons
| Items | Selection sort | Merge sort |
|---|---|---|
| 8 | 28 | 14 |
| 16 | 120 | 35 |
| 100 | 4,950 | 538 |
| 1,000 | 499,500 | 8,415 |
Ten times more items makes selection sort about 100× slower, but merge sort only about 13× slower.
The real words
- Running time is measured by counting basic steps (comparisons, additions, assignments) as a function of the input size n.
- We usually care about the worst case: the most steps any input of size n could need.
- Big-O describes the growth rate, ignoring constants and small terms:
3n² + 5n + 2is O(n²), because for big n the n² part dwarfs everything else.
| Big-O | Name | Example | n = 1,000 |
|---|---|---|---|
| O(1) | constant | lst[5], d[key] |
1 step |
| O(log n) | logarithmic | binary search, bisection | ~10 |
| O(n) | linear | one loop over the list, linear search | 1,000 |
| O(n log n) | “n log n” | merge sort, Python’s sorted() |
~10,000 |
| O(n²) | quadratic | loop inside a loop, selection sort | 1,000,000 |
| O(2ⁿ) | exponential | trying every subset | more than atoms in the universe |
- How to estimate: one loop over n items → O(n). A loop inside a loop, both over n → O(n²). Halving the problem each step → O(log n).
- Linear search checks items one by one: O(n). Binary search needs a sorted list and checks the middle, then throws away half: O(log n).
- Selection sort repeatedly finds the smallest remaining item: about n²/2 comparisons, O(n²). Merge sort splits the list in half, sorts each half, then merges them: O(n log n). You’ll build both properly in F10 and F17.
- Hidden costs:
x in some_listis O(n), butx in some_setorsome_dict[key]is O(1) on average. Choosing the right data structure is often the biggest speed-up available.
Count the steps
Both search functions return (found, steps). Finish binary_search on a SORTED list: check the middle, then keep only the half that could contain the target. Count one step per middle check.
Name that growth
for a in names: for b in names: if a != b: print(a, b). With n names, what's the Big-O?
Binary search needs one thing linear search doesn't. What?
Got it?
Finish the lesson to color it in on your map and collect its concept cards.
Did this lesson click?