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

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