Big O & Complexity
- Explain why growth rate matters more than raw speed for scaling systems
- Classify code as O(1), O(log n), O(n), O(n log n), or O(n²) by reading it
- Compare best, average, and worst cases and say which one matters when
- Estimate the space complexity of a function, not just its time
| Spaced-rep warm-up: due flashcards from Week 3 | 10 min |
| ELI5 + tech read, watch the growth-curves visualizer | 20 min |
| Guided: time it yourself + classify by reading | 35 min |
| Practice: the slow function clinic | 20 min |
| Project: complexity field guide | 25 min |
| Quiz + write your own flashcards additions | 10 min |
Builds on: Day 4 — Collections — lists and dicts · Day 11 — Iterators & generators
Two chefs each claim they can cater a wedding. Chef A makes a sandwich in 30 seconds but insists on shaking hands with every previous guest before serving the next one. Chef B takes 2 minutes per sandwich but just… makes sandwiches. For a party of 5, Chef A wins easily. For a wedding of 500, Chef A is still shaking hands at midnight — guest number 500 required 499 handshakes first — while Chef B finished hours ago.
Big O is the habit of asking "what happens to the TOTAL work as the guest list grows?" instead of "how fast is one sandwich?" It ignores the stopwatch (30 seconds vs 2 minutes) and looks at the *shape* of the workload: does doubling the guests double the work (linear), barely change it (logarithmic), or quadruple it (quadratic, like the handshakes)? The shape always wins eventually.
Every scaling conversation you will ever have — "why is the dashboard slow with 10k users when it was fine with 100?" — is a Big O conversation. AI engineering is full of them: comparing every document chunk to every other chunk is O(n²) and dies at scale, which is exactly why vector databases exist (Day 115). In interviews, complexity analysis is the shared language of every coding round; in front of a customer, it is how you explain why the demo that worked on 50 rows needs re-architecting for 5 million.
Four shapes of growth — the stopwatch lies, the shape doesn't
step 1 / 6One curve at a time. O(log n): doubling the input adds ONE step. This is binary search's shape.
Guided practice
Time it yourself — the shape appears
20 min- Create
bigo_lab.pyand paste the starter code. - It times two functions that both answer "does this list contain duplicates?" — one with a nested loop, one with a set.
- Run it for n = 1_000, 2_000, 4_000, 8_000. Record the four timings for each version.
- For each version, compute the ratio between consecutive timings. Doubling n should roughly double the O(n) version (ratio ≈ 2) and quadruple the O(n²) version (ratio ≈ 4).
- Predict before you run: at n = 16_000, what will each cost? Verify.
Classify by reading
15 minClassify each snippet's time complexity before checking the answers at the bottom of the starter file. Write your reasoning in one line each — "nested loop over n" beats a guess.
Snippets: (a) summing a list; (b) x in my_list inside a loop; (c) x in my_set inside a loop; (d) a while-loop that does n = n // 2; (e) two sequential (not nested) for-loops; (f) building all pairs from a list.
On your own
The slow function clinic
20 minYou inherit find_common(a, b) which returns items present in both lists, written with a nested loop. It takes 40 seconds on production data (two lists of ~50k items).
Your goal: (1) state its current complexity; (2) rewrite it to run in well under a second; (3) state the new complexity and the space you paid for the speed; (4) verify both return the same result on a random test case.
Hints (read only if stuck): what structure gives O(1) membership checks? What is the time-space trade you are making?
Complexity field guide
Create complexity_notes.md in your practice repo: for each rung of the ladder (O(1) → O(n²)), write one Python snippet from your OWN code so far (Days 1–21 projects count), classify it, and justify the classification in one sentence. Finish with a "smells" section: three code patterns that should trigger a complexity alarm in code review (e.g. list membership test inside a loop). Commit it — this file grows during interview prep on Day 179.
Common mistakes & misconceptions
- Thinking Big O measures speed in seconds. It measures growth shape; a slow O(n) beats a fast O(n²) once n is large enough — and only then.
- Dropping the wrong term: O(n² + n) is O(n²), but O(n·m) with two independent inputs does NOT simplify to O(n²) — keep both variables.
- Assuming `x in collection` is always cheap. It is O(1) for sets/dicts, O(n) for lists — the single most common hidden quadratic in real code.
- Reporting worst case when average case is what matters (or vice versa): hash maps are O(1) average and that is usually the honest answer, with the caveat stated.
- Forgetting space: memoization and frequency dicts buy time with O(n) memory. Interviewers ask for both; production bills you for both.
Q1. A loop over n items does a membership check `x in big_list` on each pass. Overall complexity?
Q2. Doubling the input size adds exactly ONE more step. The complexity is…
Q3. Your O(n log n) solution loses to a colleague's O(n²) one on a benchmark with n = 30. What is the best explanation?
Go deeper — curated resources
- Amortized analysis — why list.append is O(1) "on average" — Dynamic arrays double capacity; occasional O(n) copies average out to O(1) per append. Revisited when we meet dynamic arrays on Day 23.
- Both guided exercises run; timing ratios recorded and explained
- find_common rewritten to O(n) with before/after timings
- Complexity field guide committed with all five classes + three smells
- Quiz ≥ 2/3 (retake after revisiting if lower)
← Back: The set-vs-list lookup gap comes straight from Day 4 (collections) — today you learned to name its cost. The timing harness reuses Day 11's iteration patterns.
Forward →: Every pattern day this phase (Days 23–34) states its complexity up front. On Day 115 the O(n²) pain of comparing everything-to-everything is exactly why approximate nearest-neighbor indexes exist, and on Day 160 you'll do capacity estimates with the same growth-shape reasoning.
Unlocks: D23 Arrays & Hashing · D24 Two Pointers & Sliding Window · D25 Stacks & Queues · D26 Linked Lists