Chapter 17: Algorithms and Problem-Solving Strategies

"An algorithm must be seen to be believed." — Donald Knuth

Chapter Overview

You've been writing algorithms since Chapter 2 — you just didn't call them that. Every function that processes a list, every loop that searches for a value, every conditional that validates input is an algorithm: a step-by-step procedure for solving a problem. But here's the question we haven't seriously asked yet: how good are your algorithms?

"Good" doesn't just mean "it produces the right answer." It means it produces the right answer without wasting time and memory. When you're working with a list of 10 items, almost any approach is fast enough. But when Dr. Anika Patel ran her DNA analysis script on 10,000 sequence files instead of 100, it went from finishing in 2 seconds to running for over 5 hours. Same script, same logic — just more data. That's not a bug you can fix with a typo correction. That's an algorithm problem.

This chapter introduces the tools for thinking about algorithm quality. You'll learn Big-O notation — the lingua franca that computer scientists use to describe how an algorithm's running time grows as input gets bigger. You'll meet three foundational problem-solving strategies: brute force, greedy, and divide and conquer. And you'll practice the skill that separates people who write code from people who understand code: analyzing algorithms before you run them.

In this chapter, you will learn to: - Evaluate algorithms for correctness, efficiency, and clarity - Use Big-O notation to classify growth rates - Recognize common complexity classes and what they mean in practice - Analyze simple loops and nested loops by counting operations - Choose among brute-force, greedy, and divide-and-conquer strategies - Write pseudocode and trace algorithms by hand

🏃 Fast Track: If you're comfortable with the idea that nested loops are slower than single loops, jump to section 17.2 for Big-O notation and then 17.5–17.7 for problem-solving strategies.

🔬 Deep Dive: After this chapter, work through Case Study 1 (Traveling Salesperson) and Case Study 2 (How Google Searches) for real-world applications of these concepts.

17.1 What Makes a Good Algorithm?

Back in Chapter 1, we defined an algorithm as a step-by-step procedure for solving a problem. That definition is accurate, but it's incomplete. Not all step-by-step procedures are equally useful. Consider two approaches to finding the largest number in a list:

Approach A: Sort and grab

def find_max_sort(numbers: list[int]) -> int:
    """Find the maximum by sorting the entire list."""
    sorted_numbers = sorted(numbers)
    return sorted_numbers[-1]

scores = [72, 95, 88, 63, 91, 84, 77]
print(find_max_sort(scores))

Output:

95

Approach B: Single pass

def find_max_scan(numbers: list[int]) -> int:
    """Find the maximum by scanning once through the list."""
    best = numbers[0]
    for score in numbers[1:]:
        if score > best:
            best = score
    return best

scores = [72, 95, 88, 63, 91, 84, 77]
print(find_max_scan(scores))

Output:

95

Both produce the correct answer. But Approach B does less work. Sorting rearranges the entire list just to find one value — that's like lining up every book in the library from thinnest to thickest when all you wanted was the thickest one. Approach B walks through the list once, keeping track of the largest value seen so far. For 7 scores, the difference is negligible. For 7 million scores, it's substantial.

A good algorithm has three properties:

1. Correctness — It produces the right answer for every valid input, not just the ones you tested. This includes edge cases: empty lists, single elements, lists where every element is the same, negative numbers.

2. Efficiency — It doesn't waste time or memory. The key insight of this chapter is that efficiency isn't about absolute speed ("it takes 0.3 seconds") — it's about how running time grows as input grows.

3. Clarity — It's understandable to other humans (and to you in six months). A clever trick that saves one millisecond but takes twenty minutes to understand is usually a bad trade-off.

🔗 Connection to Chapter 13: Testing (Chapter 13) helps you verify correctness. This chapter gives you the tools to evaluate efficiency. Together, they're how professionals assess code quality.

17.1.1 The Grade Calculator Revisited

Remember the grade calculator from earlier chapters? Let's say we want to find a student's highest score from a list of assignment grades. Here are two implementations:

# Version 1: Check every pair (O(n²) — we'll explain this notation soon)
def highest_score_pairs(grades: list[float]) -> float:
    """Find highest grade by comparing every pair."""
    for i in range(len(grades)):
        is_max = True
        for j in range(len(grades)):
            if grades[j] > grades[i]:
                is_max = False
                break
        if is_max:
            return grades[i]
    return grades[0]  # fallback

# Version 2: Single scan (O(n))
def highest_score_scan(grades: list[float]) -> float:
    """Find highest grade in a single pass."""
    best = grades[0]
    for grade in grades[1:]:
        if grade > best:
            best = grade
    return best

test_grades = [88.5, 92.0, 76.3, 95.1, 84.7]
print(f"Pairs method: {highest_score_pairs(test_grades)}")
print(f"Scan method:  {highest_score_scan(test_grades)}")

Output:

Pairs method: 95.1
Scan method:  95.1

Both are correct. But Version 1 can end up comparing every grade against every other grade — in the worst case, that's roughly n² comparisons for n grades. (The break lets it quit early on lucky inputs, but a list like [80, 80, 80, ..., 81] forces it to do nearly all of them.) Version 2 scans once — that's n comparisons, every time. With 30 students, who cares? With 300,000 records in a school district database, Version 1 can do up to 90 billion comparisons while Version 2 does 300,000. We need a way to express this difference precisely.

17.2 Measuring Efficiency: Big-O Notation

When computer scientists talk about how fast an algorithm is, they don't talk about seconds or milliseconds. Those depend on your computer's hardware, what else is running, and how the wind is blowing. Instead, they talk about how the number of operations grows relative to the size of the input.

Big-O notation is the standard way to express this growth rate. When we say an algorithm is O(n), we mean that the number of operations it performs grows linearly with the input size n. Double the input, roughly double the work. When we say it's O(n²), we mean the work grows with the square of the input. Double the input, quadruple the work.

17.2.1 Counting Operations

Let's count the operations in a simple function:

def sum_list(numbers: list[int]) -> int:
    """Sum all numbers in a list."""
    total = 0              # 1 operation (assignment)
    for num in numbers:    # runs n times
        total += num       # 1 operation per iteration
    return total           # 1 operation

print(sum_list([10, 20, 30, 40, 50]))

Output:

150

How many operations? One assignment at the start, n additions in the loop, and one return. That's n + 2 operations total. In Big-O, we drop the constants and lower-order terms: O(n).

Why drop the constants? Because Big-O describes the shape of growth, not the exact count. Whether an algorithm does 3n + 7 operations or n + 2 operations, both grow linearly. When n is a million, the difference between 3,000,007 and 1,000,002 is trivial compared to the difference between n and n².

🚪 Threshold Concept: Big-O Growth Rate Thinking

This is one of those ideas that fundamentally changes how you evaluate code.

Before this clicks: "My program takes 0.5 seconds — that's fine." After this clicks: "My program is O(n²). Right now it takes 0.5 seconds on 1,000 items. On 1,000,000 items, that's 500,000 seconds — almost six days. I need a better algorithm."

Big-O thinking is about the future. Your program might be fast enough today, but will it be fast enough when the data grows? If your algorithm is O(n), doubling the data doubles the time — manageable. If it's O(n²), doubling the data quadruples the time — and that compounds fast.

Once you internalize this, you stop asking "is this fast enough?" and start asking "how does this scale?"

17.2.2 The Rules of Big-O

Three rules simplify Big-O analysis:

1. Drop constants. O(3n) becomes O(n). O(100n²) becomes O(n²). Constants don't affect the growth shape.

2. Drop lower-order terms. O(n² + n) becomes O(n²). As n gets large, n² dominates so completely that n is irrelevant. (When n = 1,000,000: n² is 1,000,000,000,000 while n is just 1,000,000.)

3. Focus on the worst case (unless stated otherwise). Big-O typically describes the worst-case scenario — the input that makes your algorithm work the hardest.

def example_operations(n: int) -> None:
    """Demonstrate operation counting."""
    # Section A: O(1) — constant work
    x = 42
    y = x * 2

    # Section B: O(n) — linear work
    for i in range(n):
        print(i, end=" ")
    print()

    # Section C: O(n²) — quadratic work
    for i in range(n):
        for j in range(n):
            pass  # imagine some computation here

    # Total: O(1) + O(n) + O(n²) = O(n²)  (drop lower terms)

example_operations(5)

Output:

0 1 2 3 4

The total complexity is O(1) + O(n) + O(n²). By rule 2, we drop O(1) and O(n), leaving O(n²) — the most dominant term dictates the overall growth.

17.3 Common Complexity Classes

Here are the complexity classes you'll encounter most often, from fastest to slowest, with rough step counts for each input size:

Let's see each in Python.

17.3.1 O(1) — Constant Time

The algorithm does the same amount of work regardless of input size.

def get_first(items: list) -> object:
    """Return the first element. O(1) — doesn't matter how long the list is."""
    return items[0]

small_list = [1, 2, 3]
huge_list = list(range(10_000_000))

print(get_first(small_list))  # Same speed
print(get_first(huge_list))   # Same speed

Output:

1
0

Accessing a list element by index is O(1). Python stores lists as arrays in memory — it can jump directly to any position.

🔄 Spaced Review — Chapter 9: Remember dictionary lookups? Looking up grades["Alice"] in a dict is O(1) on average — Python uses a hash table to jump directly to the value. Chapter 9 borrowed the "O(1)" label before we'd defined it; now you know exactly what it promises: the work stays about the same no matter how many keys the dict holds. Compare that to searching a list for "Alice" — that's O(n), because you might have to check every element.

17.3.2 O(log n) — Logarithmic Time

The algorithm cuts the problem in half at each step. The classic example is binary search (which you'll implement in Chapter 19), but here's the intuition:

def count_halvings(n: int) -> int:
    """Count how many times you can halve n before reaching 1. O(log n)."""
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

print(f"Halvings for 8:         {count_halvings(8)}")
print(f"Halvings for 1,000:     {count_halvings(1_000)}")
print(f"Halvings for 1,000,000: {count_halvings(1_000_000)}")

Output:

Halvings for 8:         3
Halvings for 1,000:     9
Halvings for 1,000,000: 19

Look at that. A million items only needs 19 halvings. That's the power of logarithmic algorithms — they barely notice when the input grows. Going from 1,000 to 1,000,000 (a 1,000x increase) only added 10 steps.

17.3.3 O(n) — Linear Time

Work grows directly with input size. You saw this with sum_list() above. Here's another example:

def contains(items: list, target) -> bool:
    """Check if target is in the list. O(n) worst case."""
    for item in items:
        if item == target:
            return True   # best case: O(1) — found it first
    return False          # worst case: O(n) — checked everything

print(contains([4, 8, 15, 16, 23, 42], 23))
print(contains([4, 8, 15, 16, 23, 42], 99))

Output:

True
False

In the worst case (target isn't there), we check every element — that's O(n). In the best case (target is first), it's O(1). Big-O typically refers to worst case.

17.3.4 O(n²) — Quadratic Time

Usually caused by nested loops where both loops depend on n. This is where things get painful:

def find_duplicates(items: list) -> list:
    """Find duplicates by comparing every pair. O(n²)."""
    duplicates = []
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j] and items[i] not in duplicates:
                duplicates.append(items[i])
    return duplicates

names = ["Alice", "Bob", "Charlie", "Alice", "Diana", "Bob"]
print(find_duplicates(names))

Output:

['Alice', 'Bob']

Every element is compared with every other element. For 6 names, that's about 15 comparisons. For 6,000 names, that's about 18 million. For 6 million names, it's about 18 trillion. The O(n²) pattern shows up whenever you have two nested loops that both iterate over the input.

🔗 Connection to Chapter 9: You could find duplicates in O(n) using a set: python def find_duplicates_fast(items: list) -> list: seen = set() reported = set() duplicates = [] for item in items: if item in seen and item not in reported: duplicates.append(item) reported.add(item) seen.add(item) return duplicates Since item in seen and item not in reported are both O(1) on average for sets (hash table lookups), the whole function is O(n). Notice the second set: checking item not in duplicates on the list would sneak an O(n) scan back into the loop. Data structure choice matters — on every line.

🔄 Check Your Understanding #1

Consider this function:

def mystery(n: int) -> int:
    total = 0
    for i in range(n):
        for j in range(10):
            total += 1
    return total

What is the Big-O complexity?

17.4 Analyzing Simple Algorithms

Let's build the skill of reading code and determining its complexity. This is algorithm analysis — one of the most important skills in computer science.

17.4.1 Worked Example: Counting Operations in a Nested Loop

def print_pairs(n: int) -> None:
    """Print all pairs (i, j) where 0 <= i < j < n."""
    pair_count = 0
    for i in range(n):           # outer: runs n times
        for j in range(i + 1, n):  # inner: runs (n-1), (n-2), ..., 1, 0 times
            print(f"({i}, {j})", end="  ")
            pair_count += 1
    print(f"\nTotal pairs: {pair_count}")

print_pairs(5)

Output:

(0, 1)  (0, 2)  (0, 3)  (0, 4)  (1, 2)  (1, 3)  (1, 4)  (2, 3)  (2, 4)  (3, 4)
Total pairs: 10

Let's trace the inner loop's execution count: - When i = 0: inner loop runs 4 times (j = 1, 2, 3, 4) - When i = 1: inner loop runs 3 times (j = 2, 3, 4) - When i = 2: inner loop runs 2 times (j = 3, 4) - When i = 3: inner loop runs 1 time (j = 4) - When i = 4: inner loop runs 0 times

Total: 4 + 3 + 2 + 1 + 0 = 10. The general formula is n(n-1)/2, which expands to (n² - n)/2. Drop the constant (1/2) and the lower-order term (n), and we get O(n²).

17.4.2 Dr. Patel's File Processing Problem

Dr. Anika Patel has a script that checks whether any two DNA sequences in her dataset are identical. Her first approach:

import time

def find_duplicate_sequences_slow(sequences: list[str]) -> list[tuple[int, int]]:
    """Find pairs of identical sequences. O(n²)."""
    matches = []
    for i in range(len(sequences)):
        for j in range(i + 1, len(sequences)):
            if sequences[i] == sequences[j]:
                matches.append((i, j))
    return matches

# Simulate with small data
seqs = ["ATCG", "GCTA", "ATCG", "TTAA", "GCTA", "ATCG"]
start = time.perf_counter()
result = find_duplicate_sequences_slow(seqs)
elapsed = time.perf_counter() - start
print(f"Found {len(result)} duplicate pairs in {elapsed:.6f} seconds")
for pair in result:
    print(f"  Sequences {pair[0]} and {pair[1]} match: {seqs[pair[0]]}")

time.perf_counter() is the stopwatch you met in Chapter 9: the highest-resolution clock Python offers for timing short stretches of code. Only the difference between two readings means anything.

Output (your timings will differ):

Found 4 duplicate pairs in 0.000013 seconds
  Sequences 0 and 2 match: ATCG
  Sequences 0 and 5 match: ATCG
  Sequences 1 and 4 match: GCTA
  Sequences 2 and 5 match: ATCG

With 6 sequences, it's instant. But Dr. Patel's real dataset has 10,000 sequences. That's 10,000 × 9,999 / 2 ≈ 50 million comparisons. And each comparison involves comparing two strings that could be thousands of characters long. No wonder it takes hours.

A smarter approach uses a dictionary to group sequences:

def find_duplicate_sequences_fast(sequences: list[str]) -> list[tuple[int, int]]:
    """Find pairs of identical sequences using a dict.

    O(n) to group, plus one step per matching pair reported.
    """
    index_map: dict[str, list[int]] = {}
    for i, seq in enumerate(sequences):
        if seq not in index_map:
            index_map[seq] = []
        index_map[seq].append(i)

    matches = []
    for indices in index_map.values():
        if len(indices) > 1:
            for i in range(len(indices)):
                for j in range(i + 1, len(indices)):
                    matches.append((indices[i], indices[j]))
    return matches

seqs = ["ATCG", "GCTA", "ATCG", "TTAA", "GCTA", "ATCG"]
start = time.perf_counter()
result = find_duplicate_sequences_fast(seqs)
elapsed = time.perf_counter() - start
print(f"Found {len(result)} duplicate pairs in {elapsed:.6f} seconds")

Output:

Found 4 duplicate pairs in 0.000009 seconds

The dictionary approach groups sequences by value in a single pass — O(n) for the grouping step. The pair generation within groups depends on the number of duplicates, not the total number of sequences. (In the extreme case where every sequence is identical, there are n(n-1)/2 matching pairs to report, and no algorithm can list them faster than that.) For most real datasets, where duplicates are rare, this is dramatically faster.

🧩 Productive Struggle: Two Solutions — Which Is Faster?

Here are two functions that both check whether a list contains any duplicates. Before reading the analysis, try to determine each one's Big-O complexity and which is faster for large inputs.

```python

Solution A

def has_duplicates_a(items: list) -> bool: for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False

Solution B

def has_duplicates_b(items: list) -> bool: return len(items) != len(set(items)) ```

Think about it for a minute before reading on.

Solution A is O(n²) — nested loops comparing every pair. Solution B is O(n) — building a set from the list is O(n), and len() is O(1). Solution B is faster for large inputs. But there's a trade-off: Solution B uses O(n) extra memory (for the set), while Solution A uses O(1) extra memory. Sometimes memory matters too — we'll discuss this in section 17.9.

🔄 Check Your Understanding #2

What is the Big-O of this function?

def process(items: list) -> int:
    total = 0
    for item in items:         # O(n)
        total += item
    for item in items:         # O(n)
        total += item * 2
    return total

17.5 Problem-Solving Strategy: Brute Force

Brute force means trying every possible solution and picking the one that works. It's the simplest strategy — and often the first one you should try.

17.5.1 When Brute Force Is Acceptable

Brute force is perfectly fine when: - The input is small enough that it finishes quickly - You need a correct baseline before optimizing - The problem doesn't have a known faster algorithm

Elena's report optimization: Elena needs to find which combination of three projects, out of 20 candidates, maximizes impact within her nonprofit's budget. There are C(20, 3) = 1,140 possible combinations. (C(n, k), read "n choose k," counts the ways to pick k items from n when order doesn't matter.) A brute-force check of all 1,140 takes milliseconds. Here's the idea on a shortlist of 8 candidates — the code is identical for 20. The standard library's itertools.combinations(projects, 3) does the enumerating for you: it hands back every group of 3 projects, one tuple at a time, never repeating a group in a different order.

from itertools import combinations

projects = [
    {"name": "Literacy Program", "cost": 15_000, "impact": 85},
    {"name": "Food Bank Expansion", "cost": 22_000, "impact": 92},
    {"name": "Youth Mentoring", "cost": 18_000, "impact": 78},
    {"name": "Job Training", "cost": 25_000, "impact": 95},
    {"name": "Health Screening", "cost": 12_000, "impact": 70},
    {"name": "Senior Services", "cost": 20_000, "impact": 88},
    {"name": "After-School Care", "cost": 16_000, "impact": 82},
    {"name": "Housing Support", "cost": 30_000, "impact": 97},
]

budget = 55_000

def brute_force_projects(projects: list[dict], budget: int, pick: int) -> tuple:
    """Find the best combination of 'pick' projects within budget."""
    best_combo = None
    best_impact = 0

    for combo in combinations(projects, pick):
        total_cost = sum(p["cost"] for p in combo)
        total_impact = sum(p["impact"] for p in combo)
        if total_cost <= budget and total_impact > best_impact:
            best_impact = total_impact
            best_combo = combo

    return best_combo, best_impact

winner, impact = brute_force_projects(projects, budget, 3)
print(f"Best combination (impact = {impact}):")
for p in winner:
    print(f"  {p['name']:20s}  cost: ${p['cost']:,}  impact: {p['impact']}")
total_cost = sum(p["cost"] for p in winner)
print(f"  {'Total':20s}  cost: ${total_cost:,}")

Output:

Best combination (impact = 259):
  Literacy Program      cost: $15,000  impact: 85
  Food Bank Expansion   cost: $22,000  impact: 92
  After-School Care     cost: $16,000  impact: 82
  Total                 cost: $53,000

Notice the winner doesn't even spend the whole budget: Literacy + Food Bank + Youth Mentoring costs exactly $55,000 but scores only 255. Brute force doesn't care about hunches like "use every dollar" — it checks every option and reports the facts.

With 8 projects choosing 3, there are only 56 combinations. Even with 100 projects, C(100, 3) = 161,700 — still manageable. But C(100, 10) = 17.3 trillion. Brute force has limits.

17.5.2 When Brute Force Breaks Down

The number of combinations grows explosively. This is why brute force is often O(2ⁿ) or worse — every additional element can double the work. We'll see this dramatically in Case Study 1 (Traveling Salesperson).

17.6 Problem-Solving Strategy: Greedy

A greedy algorithm makes the best possible choice at each step, without looking ahead. It's like always taking the biggest slice of pizza first — locally optimal, and sometimes globally optimal too.

17.6.1 When Greedy Works: Making Change

The classic example where greedy works perfectly is the coin change problem (with standard US denominations):

def make_change_greedy(amount: int) -> dict[int, int]:
    """Make change using the fewest coins (greedy). Works for US denominations."""
    coins = [25, 10, 5, 1]  # quarters, dimes, nickels, pennies
    result = {}

    for coin in coins:
        if amount >= coin:
            count = amount // coin
            result[coin] = count
            amount -= coin * count

    return result

change = make_change_greedy(87)
print("Change for 87 cents:")
for coin, count in change.items():
    print(f"  {coin}¢ × {count}")
total_coins = sum(change.values())
print(f"Total coins: {total_coins}")

Output:

Change for 87 cents:
  25¢ × 3
  10¢ × 1
  1¢ × 2
Total coins: 6

The greedy approach — always use the largest coin possible — gives the optimal answer for US coins. Why it works isn't obvious (a quarter isn't a multiple of a dime, after all). Coin systems where greedy always finds the fewest coins are called canonical, and the US set of 25, 10, 5, and 1 happens to be one of them. Take away the nickel, though, and greedy breaks: for 30¢ it hands you 25 + 1 + 1 + 1 + 1 + 1 (six coins) instead of three dimes.

17.6.2 When Greedy Fails

Greedy doesn't always give the optimal answer. Consider a coin system with denominations [1, 3, 4]:

def make_change_greedy_custom(amount: int, denominations: list[int]) -> dict[int, int]:
    """Greedy change-making with custom denominations."""
    coins_sorted = sorted(denominations, reverse=True)
    result = {}

    remaining = amount
    for coin in coins_sorted:
        if remaining >= coin:
            count = remaining // coin
            result[coin] = count
            remaining -= coin * count

    return result

# Greedy: for 6 cents with coins [1, 3, 4]
greedy_result = make_change_greedy_custom(6, [1, 3, 4])
print("Greedy solution for 6 cents with [1, 3, 4]:")
for coin, count in greedy_result.items():
    print(f"  {coin}¢ × {count}")
print(f"  Total coins: {sum(greedy_result.values())}")

print("\nOptimal solution: 3¢ × 2 = 2 coins")

Output:

Greedy solution for 6 cents with [1, 3, 4]:
  4¢ × 1
  1¢ × 2
  Total coins: 3

Optimal solution: 3¢ × 2 = 2 coins

Greedy picks 4¢ first (the largest coin ≤ 6), then needs two 1¢ coins — three coins total. The optimal solution uses two 3¢ coins. The greedy algorithm got trapped by its first choice.

💡 Key Insight: Greedy algorithms are fast (typically O(n log n) or better, because they usually sort once and then make a single pass) but only correct for problems with the greedy-choice property — where locally optimal choices lead to globally optimal solutions. Before using greedy, you need to convince yourself (or prove) that the property holds.

Elena's priority ranking: Elena uses a greedy approach for her daily task list — always work on the highest-impact task first. This works well for independent tasks but fails when tasks have dependencies: the highest-impact task might require completing a lower-impact task first.

17.7 Problem-Solving Strategy: Divide and Conquer

Divide and conquer breaks a problem into smaller subproblems, solves each one, and combines the results. The key insight is that the subproblems are the same type of problem, just smaller.

17.7.1 The Pattern

1. Divide the problem in half (or into roughly equal parts)
2. Conquer each part (often recursively — more in Chapter 18)
3. Combine the results

17.7.2 Example: Finding the Maximum (Divide and Conquer)

def find_max_dc(numbers: list[int]) -> int:
    """Find maximum using divide and conquer."""
    # Base case: single element
    if len(numbers) == 1:
        return numbers[0]

    # Divide: split the list in half
    mid = len(numbers) // 2
    left_half = numbers[:mid]
    right_half = numbers[mid:]

    # Conquer: find max in each half
    left_max = find_max_dc(left_half)
    right_max = find_max_dc(right_half)

    # Combine: the overall max is the larger of the two
    return left_max if left_max >= right_max else right_max

scores = [72, 95, 88, 63, 91, 84, 77, 69]
print(f"Maximum: {find_max_dc(scores)}")

Output:

Maximum: 95

This particular example makes n − 1 comparisons — exactly as many as the simple scan — so divide and conquer buys you nothing here. It's actually a little worse: every slice like numbers[:mid] copies elements into a new list, and all that copying adds up to O(n log n) work. (Passing start and end indices instead of slicing would avoid the copies.) But the pattern is what matters. Merge sort (Chapter 19) uses divide and conquer to sort in O(n log n), which is dramatically faster than the O(n²) sorting algorithms.

17.7.3 Why Divide and Conquer Is Powerful

The magic of divide and conquer comes from repeatedly halving the problem. If you halve a problem of size n, you get two problems of size n/2. If those halve again, four problems of size n/4. After log₂(n) levels of halving, you're down to problems of size 1.

Here's the intuition with a visual trace for finding the max of [72, 95, 88, 63]:

Level 0: [72, 95, 88, 63]         → need to find max
Level 1: [72, 95]    [88, 63]     → find max of each half
Level 2: [72] [95]   [88] [63]   → base cases: max is the element itself
Combine:  max=95      max=88      → each half returns its max
Combine:       max=95             → overall max

🔄 Spaced Review — Chapter 14: Classes bundle behavior into objects, so you could wrap each of these strategies in its own class with a shared solve() method. That's exactly the Strategy pattern from Chapter 16, where the Text Adventure swapped combat strategies in and out. Here, a BruteForceSolver and a GreedySolver could be interchangeable: same interface, different algorithm, chosen at runtime based on input size.

🔄 Check Your Understanding #3

Match each strategy to the scenario where it's most appropriate:

1. You need to find the two closest points among 1,000 points on a map.
2. You need to pack a backpack with the most valuable items under a weight limit (8 items available).
3. You need to schedule tasks to minimize total waiting time, and tasks are independent.

Strategies: Brute Force, Greedy, Divide and Conquer

17.8 Pseudocode and Algorithm Tracing

Before you write Python, write pseudocode — a language-independent description of your algorithm. Pseudocode lets you focus on logic without worrying about syntax.

17.8.1 Writing Pseudocode

Good pseudocode is precise enough to translate directly to code but informal enough to read quickly:

ALGORITHM: Find the two largest elements in a list
INPUT: numbers (a list of at least two numbers)
OUTPUT: (largest, second_largest)

1. SET largest = first element of numbers
2. SET second_largest = negative infinity
3. FOR each number in numbers (starting from the second):
   a. IF number > largest:
      i.  SET second_largest = largest
      ii. SET largest = number
   b. ELSE IF number > second_largest:
      i.  SET second_largest = number
4. RETURN (largest, second_largest)

And the Python translation:

def two_largest(numbers: list[float]) -> tuple[float, float]:
    """Find the two largest elements in a single pass. O(n)."""
    largest = numbers[0]
    second_largest = float("-inf")

    for num in numbers[1:]:
        if num > largest:
            second_largest = largest
            largest = num
        elif num > second_largest:
            second_largest = num

    return largest, second_largest

grades = [88, 72, 95, 91, 84, 63, 77]
first, second = two_largest(grades)
print(f"Highest: {first}, Runner-up: {second}")

Output:

Highest: 95, Runner-up: 91

17.8.2 Tracing an Algorithm

Tracing means stepping through an algorithm by hand, tracking variable values at each step. It's the most reliable way to verify correctness and build intuition.

Let's trace two_largest with [88, 72, 95, 91]:

Wait — 72 > -inf is true. Every number beats negative infinity; that's the whole point of starting there. Let me retrace:

Final result: (95, 91). Correct.

Notice that I made an error on my first trace and caught it. This happens all the time — tracing is about being honest, not being perfect. If you mess up, it means you found a spot where the algorithm might be confusing to implement, too.

✅ Best Practice: Trace your algorithm on at least three inputs before coding: 1. A "normal" case (like the one above) 2. An edge case (list with two elements, or all identical values) 3. A case that tests the boundaries (largest element first, or last)

17.9 Space Complexity

So far we've focused on time complexity — how many operations an algorithm performs. Space complexity measures how much memory an algorithm uses beyond the input itself.

17.9.1 Common Space Complexities

# O(1) space — only uses a fixed number of variables
def sum_in_place(numbers: list[int]) -> int:
    total = 0
    for num in numbers:
        total += num
    return total

# O(n) space — creates a new list the same size as input
def doubled(numbers: list[int]) -> list[int]:
    return [num * 2 for num in numbers]

data = [10, 20, 30, 40, 50]
print(f"Sum: {sum_in_place(data)}")
print(f"Doubled: {doubled(data)}")

Output:

Sum: 150
Doubled: [20, 40, 60, 80, 100]

17.9.2 Time-Space Trade-offs

There's often a trade-off between time and space. Remember the duplicate-finding example? The O(n²) solution used O(1) extra space; the O(n) solution used O(n) extra space (for the set). You trade memory for speed.

import time

def has_dupes_slow(items: list) -> bool:
    """O(n²) time, O(1) space."""
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_dupes_fast(items: list) -> bool:
    """O(n) time, O(n) space."""
    return len(items) != len(set(items))

# Compare on a larger dataset
test_data = list(range(10_000)) + [5_000]  # one duplicate at the end

start = time.perf_counter()
result_slow = has_dupes_slow(test_data)
time_slow = time.perf_counter() - start

start = time.perf_counter()
result_fast = has_dupes_fast(test_data)
time_fast = time.perf_counter() - start

print(f"Slow (O(n²)): {result_slow} in {time_slow:.4f} seconds")
print(f"Fast (O(n)):  {result_fast} in {time_fast:.4f} seconds")
print(f"Speedup: {time_slow / time_fast:.0f}x")

Output (approximate — will vary by machine):

Slow (O(n²)): True in 0.9140 seconds
Fast (O(n)):  True in 0.0004 seconds
Speedup: 2285x

A speedup of a couple of thousand times for just 10,000 items. (The duplicate sits at index 5,000, so the slow version gets to quit partway through — and it's still thousands of times slower.) At 1,000,000 items — 100 times more data — the slow version would do roughly 10,000 times more work and take hours. The fast version: still well under a second.

17.10 Project Checkpoint: TaskFlow v1.6

Time to apply algorithm analysis to our ongoing project. TaskFlow has grown from a simple to-do list into a modular, tested, object-oriented application. But we've never asked: how efficient are its operations?

What's New in v1.6

• Analyze the Big-O complexity of existing TaskFlow operations
• Add timing benchmarks to measure real performance
• Optimize the task search operation
• Add a benchmark command to the CLI

The data model doesn't change: v1.6 uses v1.5's Task dataclass exactly as Chapter 16 left it, with "high"/"medium"/"low" priorities, and it saves to the same taskflow_data.json file. To make the algorithm changes stand out, the reference version in code/project-checkpoint.py wraps that Task in plain functions over a list of tasks rather than in v1.5's TaskList class with its observers. In your own TaskFlow, the keyword index becomes one more attribute of TaskList, and each function below becomes a method.

The Key Operations to Analyze

*Appending is O(1) amortized: once in a while Python has to move the list to a bigger block of memory, but that cost averages out to a constant per append.

†Deleting from the middle of a list is O(n) because elements after the deletion point must shift.

Your Assignment

A finished reference version of TaskFlow v1.6 is in code/project-checkpoint.py. Try building these features yourself before you peek:

1. Add a benchmark command that generates n dummy tasks and times each operation
2. Optimize search by maintaining a keyword index (a dict mapping words to task indices)
3. Document the Big-O of every public method in its docstring
4. Add timing output that shows how long operations took when run on large datasets

Here's the key addition, the benchmark() function from code/project-checkpoint.py. It builds n dummy tasks, then times a linear search, an indexed search, a sort, and the one-time cost of building the index. (search_tasks_linear(), search_tasks_indexed(), sort_tasks_by_priority(), and the KeywordIndex class are the operations you're optimizing; each one's docstring states its Big-O.)

import time


def benchmark(sizes: list[int] | None = None) -> None:
    """Benchmark TaskFlow operations at various scales."""
    if sizes is None:
        sizes = [100, 500, 1_000, 5_000, 10_000]

    print(f"\n  {'Size':>8}  {'Linear Search':>15}  {'Indexed Search':>16}  "
          f"{'Sort':>10}  {'Index Build':>13}")
    print("  " + "-" * 68)

    for n in sizes:
        # Generate test tasks
        tasks = [
            Task(
                title=f"Task number {i} in category {i % 10}",
                priority=["high", "medium", "low"][i % 3],
                category=f"cat-{i % 10}",
            )
            for i in range(n)
        ]

        # Build keyword index
        idx = KeywordIndex()
        start = time.perf_counter()
        idx.build(tasks)
        build_time = time.perf_counter() - start

        # Benchmark: linear search
        keyword = f"task number {n // 2}"
        start = time.perf_counter()
        search_tasks_linear(tasks, keyword)
        linear_time = time.perf_counter() - start

        # Benchmark: indexed search for the same task. Its number is a word
        # that appears in only that one title.
        start = time.perf_counter()
        search_tasks_indexed(idx, str(n // 2))
        indexed_time = time.perf_counter() - start

        # Benchmark: sort
        start = time.perf_counter()
        sort_tasks_by_priority(tasks)
        sort_time = time.perf_counter() - start

        print(f"  {n:>8,}  {linear_time:>14.6f}s  {indexed_time:>15.6f}s  "
              f"{sort_time:>9.6f}s  {build_time:>12.6f}s")

    print("\n  Big-O summary:")
    print("    Linear search:  O(n)      — time scales with task count")
    print("    Indexed search: O(1)      — time stays constant")
    print("    Sort:           O(n log n) — grows, but slowly")
    print("    Index build:    O(n * w)  — one-time cost, amortized over searches")

Run it with three sizes, each ten times bigger than the last:

benchmark([100, 1_000, 10_000])

Sample output (yours will differ):

      Size    Linear Search    Indexed Search        Sort    Index Build
  --------------------------------------------------------------------
       100        0.000007s         0.000002s   0.000023s      0.000086s
     1,000        0.000064s         0.000004s   0.000070s      0.000739s
    10,000        0.000678s         0.000004s   0.000608s      0.063276s

  Big-O summary:
    Linear search:  O(n)      — time scales with task count
    Indexed search: O(1)      — time stays constant
    Sort:           O(n log n) — grows, but slowly
    Index build:    O(n * w)  — one-time cost, amortized over searches

Read the ratios, not the raw numbers. Each 10x jump in tasks makes the linear search about 10x slower, which is linear, as predicted, while the indexed search barely moves. The sort also grows roughly in step with n; the extra log n factor in O(n log n) is hard to spot at these sizes because log n grows so slowly (it only goes from about 7 to about 13 here). The index build is the price of fast searches: it touches every word of every title once, so it's worth paying only if you search more than once. Timings this small are noisy, so run the benchmark a few times before trusting any single number.

🔗 Bridge to Chapter 18: In Chapter 18 (Recursion), you'll see how divide and conquer is implemented using recursive function calls. The find_max_dc example from section 17.7 will become natural once you understand how functions can call themselves. In Chapter 19, you'll implement real searching and sorting algorithms and analyze their complexities rigorously.

Chapter Summary

This chapter introduced the fundamental tools for thinking about algorithm quality:

• Big-O notation describes how an algorithm's running time grows as input size increases. It ignores constants and lower-order terms to focus on the growth shape.
• Common complexity classes range from O(1) (constant — the best) through O(log n), O(n), O(n log n), to O(n²) (quadratic — often problematic for large inputs).
• Algorithm analysis involves counting operations, especially in loops and nested loops, to determine complexity.
• Brute force tries every possibility. It's simple and correct but only feasible for small inputs.
• Greedy makes the locally best choice at each step. It's fast but only works when local optima lead to global optima.
• Divide and conquer splits problems in half, solves each half, and combines results. It often achieves O(n log n) complexity.
• Pseudocode and tracing help you design and verify algorithms before writing code.
• Space complexity measures memory usage and often involves trade-offs with time complexity.

The core insight of this chapter — the threshold concept — is that growth rate matters more than absolute speed. An O(n²) algorithm that's fast on 100 items will be agonizingly slow on 100,000 items. An O(n) algorithm that seems slightly slower on 100 items will be roughly a thousand times faster on 100,000, because 1,000 times more data means 1,000 times more work for one and a million times more for the other.

What's next: Chapter 18 explores recursion — the technique that makes divide and conquer elegant. Chapter 19 uses everything from this chapter to analyze real searching and sorting algorithms.