Key Takeaways: Algorithms and Problem-Solving Strategies

One-Sentence Summary

Big-O notation tells you how an algorithm's running time grows as input grows — and that growth rate matters far more than how fast it runs today on small data.

The Three Properties of a Good Algorithm

Property What It Means How to Verify
Correctness Right answer for every valid input, including edge cases Testing (Ch 13), tracing by hand
Efficiency Doesn't waste time or memory as input grows Big-O analysis
Clarity Understandable to others (and future you) Pseudocode, comments, clean structure

Big-O Complexity Classes at a Glance

Big-O Name Pattern Real-World Feel
O(1) Constant Dict lookup, list index access Instant, always
O(log n) Logarithmic Halving the problem each step Barely notice growth
O(n) Linear Single loop through all elements Scales gracefully
O(n log n) Linearithmic Efficient sorting (merge sort) Fast enough for most things
O(n²) Quadratic Nested loops over same data Painful past ~10,000 items

Big-O Rules

  1. Drop constants: O(3n) = O(n)
  2. Drop lower-order terms: O(n² + n) = O(n²)
  3. Focus on worst case (unless stated otherwise)

Three Problem-Solving Strategies

Strategy Approach Speed When to Use
Brute force Try every possibility Often O(2ⁿ) or O(n!) Small inputs; when you need a correct baseline
Greedy Best local choice at each step Often O(n log n) When local optima lead to global optima
Divide and conquer Split, solve halves, combine Often O(n log n) When the problem can be halved naturally

Habits Worth Keeping

  • Sequential loops add; nested loops multiply. Two back-to-back O(n) loops are still O(n); an O(n) loop inside another O(n) loop is O(n²).
  • Data structure choice is an algorithm choice. Swapping a list for a set or dict turns an O(n) membership test into O(1) on average.
  • Pseudocode first, then trace. Walk through a normal case, an edge case, and a boundary case by hand before you code.
  • Count memory too. Space complexity measures extra memory; faster algorithms often buy their speed with it (the set-based duplicate check uses O(n) extra space).
  • Measure with time.perf_counter(). Compare how times grow as n grows, not the raw numbers.

Key Distinctions

What Beginners Think What's Actually True
"My program is fast enough" What matters is how it scales to 10x or 100x more data
"Nested loops are always O(n²)" Only if both loops depend on n
"Greedy always works" Greedy only works for problems with the greedy-choice property
"The fastest algorithm is always best" Time-space trade-offs mean faster algorithms may use more memory
"Big-O tells you exact run time" Big-O describes growth shape, not absolute speed

Threshold Concept: Growth Rate Thinking

Before: "It runs in 0.5 seconds, that's fine."

After: "It's O(n²). It runs in 0.5 seconds on 1,000 items. On 1,000,000 items, that's 500,000 seconds — nearly six days."

What's Next

  • Chapter 18 (Recursion): The technique that makes divide and conquer elegant — functions that call themselves
  • Chapter 19 (Searching and Sorting): Apply Big-O analysis to classic algorithms: binary search, selection sort, merge sort