Algorithm Analysis and Problem Solving

Summary

This chapter deepens students' understanding of algorithm analysis and introduces problem-solving strategies. Students will learn about logarithmic and linearithmic time complexity, best/average/worst case analysis, empirical analysis, and counting operations. The chapter covers algorithmic strategies including brute force, divide and conquer, and greedy approaches. Common programming patterns like two pointer, sliding window, and frequency counter are introduced. Memoization is covered as an optimization technique that bridges recursion and dictionaries.

Concepts Covered

This chapter covers the following 16 concepts from the learning graph:

1. Logarithmic Time O(log n)
2. Linearithmic Time
3. Best Average Worst Case
4. Empirical Analysis
5. Counting Operations
6. Brute Force Approach
7. Divide and Conquer
8. Greedy Algorithms
9. Algorithm Tradeoffs
10. Efficiency vs Readability
11. Two Pointer Technique
12. Sliding Window Pattern
13. Frequency Counter Pattern
14. Recursion in Algorithms
15. Algorithm Visualization
16. Memoization

Prerequisites

This chapter builds on concepts from:

• Chapter 2: Python Fundamentals
• Chapter 7: Higher-Order Functions and Recursion
• Chapter 8: Lists
• Chapter 11: Dictionaries
• Chapter 17: Testing and Debugging
• Chapter 18: Searching and Sorting

---

Monty says: Let's code this!

Welcome back, coders! In Chapter 18 you learned the basics of Big-O notation and saw how different sorting algorithms compare. Now we're going to level up. You'll learn why some algorithms seem almost magical in their speed, discover powerful problem-solving strategies, and pick up programming patterns that real software engineers use every day. Ready to think like an algorithm designer? Let's do this!

Beyond Linear: Logarithmic Time

In Chapter 18 you met ( O(1) ), ( O(n) ), and ( O(n^2) ). But there's a complexity class that sits between constant and linear time, and it's one of the most exciting ones in all of computer science.

Logarithmic Time ( O(\log n) ) describes algorithms where each step cuts the remaining work in half. Binary search is the classic example. If you have a sorted list of 1,000 items, binary search needs at most about 10 comparisons. Double the list to 2,000 items? You only need about 11 comparisons. That's the power of logarithms.

Here's the intuition: a logarithm answers the question "how many times can I divide this number by 2 before I reach 1?" For ( n = 1{,}024 ), the answer is 10, because ( 2^{10} = 1{,}024 ). So ( \log_2(1{,}024) = 10 ).

def binary_search(sorted_list, target):
    """O(log n) — cuts the search space in half each step."""
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # not found

Why does this matter? Imagine searching through a phone book with one million names. A linear search might need up to 1,000,000 comparisons. Binary search? About 20. That's not a small improvement — that's the difference between waiting a minute and getting your answer in a blink.

Linearithmic Time: The Sweet Spot

Now let's meet Linearithmic Time, also written ( O(n \log n) ). This is the time complexity of efficient sorting algorithms like merge sort, quicksort (on average), and Python's built-in sorted() function (which uses Timsort).

Think of it as "do something logarithmic for each of the ( n ) items." Merge sort, for example, divides the list in half repeatedly (( \log n ) levels of splitting), and at each level it does ( O(n) ) work to merge everything back together.

Here's the key fact: you cannot sort a list of arbitrary items faster than ( O(n \log n) ) using comparisons. This is a mathematical proof, not just a practical limit. So when you see an ( O(n \log n) ) sorting algorithm, you're looking at the best possible general-purpose sort.

Complexity Class Comparison Chart

Diagram:

Complexity Class	Name	Example	Operations for ( n = 1{,}000 )
( O(1) )	Constant	Dictionary lookup	1
( O(\log n) )	Logarithmic	Binary search	~10
( O(n) )	Linear	Linear search	1,000
( O(n \log n) )	Linearithmic	Merge sort	~10,000
( O(n^2) )	Quadratic	Selection sort	1,000,000
( O(2^n) )	Exponential	All subsets	( \approx 10^{301} )

Notice how the jump from ( O(n \log n) ) to ( O(n^2) ) is a factor of 100 at ( n = 1{,}000 ). At ( n = 1{,}000{,}000 ), that factor becomes 50,000. The difference between "good enough" and "unacceptable" is often one complexity class.

Best, Average, and Worst Case

So far we've mostly talked about worst-case complexity. But algorithms don't always behave the same way on every input. Best Average Worst Case analysis looks at all three scenarios.

Consider linear search in a list of ( n ) items:

• Best case: The target is the very first element. ( O(1) ).
• Worst case: The target is the last element (or not present). ( O(n) ).
• Average case: On average, you'll check about half the list. ( O(n) ) — same order as worst case, but with a smaller constant.

Why does this matter? Quicksort is a great example. Its average case is ( O(n \log n) ), which is excellent. But its worst case is ( O(n^2) ), which happens when the pivot choices are terrible (like always picking the smallest or largest element). That's why Python's built-in sort uses Timsort instead of plain quicksort — Timsort guarantees ( O(n \log n) ) in the worst case.

Monty says: Let's debug this together!

When someone asks "what's the time complexity?" they usually mean the worst case unless they say otherwise. The worst case is the safest guarantee — it tells you the maximum time your program will ever need.

Counting Operations

Before you can classify an algorithm's complexity, you need to know how to count operations. This means stepping through your code and tallying how many times each line runs as a function of the input size ( n ).

Let's count the operations in a simple function:

def sum_of_squares(n):
    total = 0              # 1 assignment
    for i in range(n):     # loop runs n times
        total += i * i     # 1 multiplication + 1 addition per iteration
    return total           # 1 return

The assignment and return each happen once: that's 2 operations. Inside the loop, we do 2 operations per iteration, and the loop runs ( n ) times. Total: ( 2n + 2 ) operations. In Big-O, we drop the constants and lower-order terms: ( O(n) ).

Now let's count a nested loop:

def all_pairs(items):
    count = 0
    for i in range(len(items)):         # n iterations
        for j in range(len(items)):     # n iterations each
            count += 1                  # 1 operation
    return count

The inner operation runs ( n \times n = n^2 ) times, so this is ( O(n^2) ).

Operation Counting Walkthrough

Diagram:

Here's a step-by-step trace for sum_of_squares(4):

Step	i	Operation	total
1	—	total = 0	0
2	0	total += 0 * 0	0
3	1	total += 1 * 1	1
4	2	total += 2 * 2	5
5	3	total += 3 * 3	14
6	—	return 14	14

Total loop body executions: 4 (which is ( n )). Total operations: ( 2 \times 4 + 2 = 10 ). Simplified: ( O(n) ).

Empirical Analysis: Measuring Real Performance

Theory is great, but sometimes you just want to see the numbers. Empirical Analysis means running your code, measuring the actual time it takes, and looking for patterns. Python's time module makes this easy.

import time

def time_algorithm(func, *args):
    """Measure the execution time of a function."""
    start = time.time()
    result = func(*args)
    end = time.time()
    return end - start, result

# Compare linear search vs binary search
import random

def linear_search(lst, target):
    for i, val in enumerate(lst):
        if val == target:
            return i
    return -1

sizes = [10_000, 50_000, 100_000, 500_000, 1_000_000]

print(f"{'Size':>10} {'Linear (s)':>12} {'Binary (s)':>12}")
print("-" * 36)

for n in sizes:
    data = list(range(n))
    target = n - 1  # worst case: last element

    t_linear, _ = time_algorithm(linear_search, data, target)
    t_binary, _ = time_algorithm(binary_search, data, target)

    print(f"{n:>10,} {t_linear:>12.6f} {t_binary:>12.6f}")

When you run this, you'll see linear search times growing proportionally with ( n ), while binary search times barely change. That's the difference between ( O(n) ) and ( O(\log n) ) made visible.

Monty says: Let's debug this together!

When doing empirical analysis, run each test several times and take the average. Other programs running on your computer can cause timing noise. Also, use large enough inputs — with ( n = 10 ), everything looks fast!

Algorithmic Strategies

Now that you can analyze algorithms, let's talk about how to design them. There are several classic strategies that programmers reach for when facing a new problem.

Brute Force: Try Everything

The Brute Force Approach is the simplest strategy: try every possible solution and pick the best one. It's not clever, but it's reliable. You're guaranteed to find the answer because you've checked everything.

For example, to find two numbers in a list that add up to a target:

def two_sum_brute(numbers, target):
    """Brute force: check every pair. O(n^2)."""
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return (i, j)
    return None

This works, but with nested loops it's ( O(n^2) ). For large lists, that's painfully slow. Brute force is a great starting point — get something working, then optimize.

Divide and Conquer

Divide and Conquer is a strategy where you break a problem into smaller subproblems, solve each one, and combine the results. Merge sort is the textbook example:

1. Divide: Split the list in half.
2. Conquer: Sort each half (recursively).
3. Combine: Merge the two sorted halves.

def merge_sort(lst):
    """Divide and conquer sorting. O(n log n)."""
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Divide and conquer works brilliantly when you can split a problem into independent subproblems of roughly equal size. Other examples include binary search and the fast Fourier transform.

Greedy Algorithms

A Greedy Algorithm makes the best local choice at each step, hoping that these local choices lead to a globally optimal solution. Greedy algorithms don't look ahead or reconsider past decisions — they just grab the best option right now.

Classic example: the coin change problem. You need to make change for 67 cents using the fewest coins possible (quarters, dimes, nickels, pennies).

def greedy_coin_change(amount):
    """Greedy approach to coin change. Works for US coins."""
    coins = [25, 10, 5, 1]
    result = []

    for coin in coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin

    return result

print(greedy_coin_change(67))
# Output: [25, 25, 10, 5, 1, 1]  -> 6 coins

The greedy approach works perfectly for US coins. But beware: greedy algorithms don't always give the optimal solution. If our coin denominations were [25, 15, 1], trying to make 30 cents greedily gives [25, 1, 1, 1, 1, 1] (6 coins), but the optimal answer is [15, 15] (2 coins). Greedy algorithms need to be proven correct for each specific problem.

Strategy Comparison Diagram

Diagram:

Strategy	Approach	When to Use	Guarantee
Brute Force	Try all possibilities	When the input is small, or as a first draft	Always finds the answer
Divide and Conquer	Split, solve, combine	When the problem splits into independent subproblems	Correct if subproblems are independent
Greedy	Best local choice at each step	When local optima lead to global optimum	Must be proven for each problem

Brute force is your safety net. Divide and conquer is your power tool. Greedy is your shortcut — but only when the road is straight.

Algorithm Tradeoffs

Every algorithm involves Algorithm Tradeoffs. The most common tradeoff is time vs. space: you can often make an algorithm faster by using more memory, or save memory by accepting a slower runtime.

For example, consider checking if a list has duplicate values:

# Time-optimized: O(n) time, O(n) space
def has_duplicates_fast(lst):
    seen = set()
    for item in lst:
        if item in seen:
            return True
        seen.add(item)
    return False

# Space-optimized: O(n^2) time, O(1) space
def has_duplicates_slow(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j]:
                return True
    return False

The first version uses a set (extra memory) to achieve ( O(n) ) time. The second version uses no extra memory but takes ( O(n^2) ) time. Which is better? It depends on your situation. If memory is tight (like on an embedded device), the slow version might be the right choice.

Efficiency vs. Readability

Efficiency vs Readability is another important tradeoff. Code that's hyper-optimized can be hard to understand and maintain. Code that's beautifully readable might be too slow for large inputs.

# Readable but slower: O(n)
def is_palindrome_readable(s):
    return s == s[::-1]

# Efficient and still pretty readable: O(n) — same big-O,
# but uses half the memory (no reversed copy)
def is_palindrome_efficient(s):
    left = 0
    right = len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Both are ( O(n) ), but the first creates a reversed copy of the string (extra memory), while the second uses two pointers and constant extra space. In most cases, the readable version is perfectly fine. Save the clever optimizations for when profiling tells you there's a real bottleneck.

Monty says: Watch out!

Don't optimize code that doesn't need optimizing! Write clear, correct code first. Only optimize if your program is actually too slow — and use empirical analysis to find the real bottleneck. Premature optimization is the root of all evil (well, at least in programming).

Programming Patterns

Let's learn three powerful patterns that show up in coding interviews, competitions, and real-world programming. These patterns turn ( O(n^2) ) brute force solutions into elegant ( O(n) ) solutions.

The Two Pointer Technique

The Two Pointer Technique uses two index variables that move through a data structure (usually a sorted list) from different positions. This avoids the nested loops that make brute force slow.

Problem: Given a sorted list of numbers, find two numbers that add up to a target sum.

def two_sum_sorted(numbers, target):
    """Two pointer approach. O(n) for sorted input."""
    left = 0
    right = len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1     # need a bigger sum
        else:
            right -= 1    # need a smaller sum

    return None

# Example
sorted_nums = [1, 3, 5, 7, 9, 11]
print(two_sum_sorted(sorted_nums, 12))
# Output: (1, 4) — because 3 + 9 = 12

The brute force approach checks every pair: ( O(n^2) ). The two pointer approach walks inward from both ends, making at most ( n ) steps: ( O(n) ). That's a massive improvement!

The Sliding Window Pattern

The Sliding Window Pattern is used when you need to examine a contiguous subarray or substring. Instead of recalculating everything from scratch each time you shift the window, you slide it by removing the outgoing element and adding the incoming one.

Problem: Find the maximum sum of any subarray of length ( k ).

def max_subarray_sum(numbers, k):
    """Sliding window approach. O(n) instead of O(n*k)."""
    if len(numbers) < k:
        return None

    # Calculate the sum of the first window
    window_sum = sum(numbers[:k])
    max_sum = window_sum

    # Slide the window: remove the leftmost, add the new rightmost
    for i in range(k, len(numbers)):
        window_sum += numbers[i] - numbers[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example: find max sum of 3 consecutive elements
data = [2, 1, 5, 1, 3, 2]
print(max_subarray_sum(data, 3))
# Output: 9 (from subarray [5, 1, 3])

Without the sliding window, you'd recalculate the sum of each subarray from scratch: ( O(n \times k) ). With the sliding window, each element is added once and removed once: ( O(n) ).

Sliding Window Visualization

Diagram:

Here's how the window slides through [2, 1, 5, 1, 3, 2] with ( k = 3 ):

Step 1:  [2  1  5] 1  3  2    sum = 8
Step 2:   2 [1  5  1] 3  2    sum = 8-2+1 = 7
Step 3:   2  1 [5  1  3] 2    sum = 7-1+3 = 9  <- maximum!
Step 4:   2  1  5 [1  3  2]   sum = 9-5+2 = 6

At each step, we subtract the element leaving the window (left side) and add the element entering (right side). One subtraction and one addition per step — that's ( O(1) ) per slide!

The Frequency Counter Pattern

The Frequency Counter Pattern uses a dictionary (or Counter from the collections module) to count occurrences of elements. This avoids nested loops when you need to compare frequencies between two collections.

Problem: Determine if two strings are anagrams (contain exactly the same characters).

def is_anagram(s1, s2):
    """Frequency counter approach. O(n) instead of O(n^2)."""
    if len(s1) != len(s2):
        return False

    freq = {}
    for char in s1:
        freq[char] = freq.get(char, 0) + 1

    for char in s2:
        if char not in freq or freq[char] == 0:
            return False
        freq[char] -= 1

    return True

print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))    # False

A brute force approach might sort both strings and compare them (( O(n \log n) )), or check each character against all characters in the other string (( O(n^2) )). The frequency counter does it in a single pass through each string: ( O(n) ).

Python also has a built-in shortcut:

from collections import Counter

def is_anagram_short(s1, s2):
    return Counter(s1) == Counter(s2)

Recursion in Problem Solving

Recursion in Algorithms is a technique where a function calls itself to solve smaller instances of the same problem. You saw recursion in Chapter 7, but here we'll see how it powers some of the most important algorithms.

Every recursive function needs two things:

1. Base case: A condition that stops the recursion.
2. Recursive case: The function calling itself with a "smaller" input.

Here's a recursive approach to computing the power of a number efficiently:

def power(base, exponent):
    """Fast exponentiation. O(log n) instead of O(n)."""
    if exponent == 0:
        return 1
    if exponent % 2 == 0:
        half = power(base, exponent // 2)
        return half * half
    else:
        return base * power(base, exponent - 1)

print(power(2, 10))  # 1024

This is divide and conquer in action! Instead of multiplying base by itself ( n ) times (( O(n) )), we halve the exponent at each step, giving us ( O(\log n) ). For ( 2^{1000} ), that's about 10 multiplications instead of 1,000.

Recursion Tree for power(2, 8)

Diagram:

power(2, 8)
  └── half = power(2, 4)
        └── half = power(2, 2)
              └── half = power(2, 1)
                    └── 2 * power(2, 0) = 2 * 1 = 2
                  return 2
              return 2 * 2 = 4
        return 4 * 4 = 16
  return 16 * 16 = 256

Only 4 recursive calls instead of 8 multiplications. For power(2, 1024), we'd need only about 10 calls!

Algorithm Visualization

Algorithm Visualization means creating visual representations of how algorithms work step by step. Visualizations help you understand what an algorithm does at each point in its execution. They're one of the best tools for building intuition about why certain algorithms are fast or slow.

You can visualize algorithms in many ways:

• Trace tables — manually track variables at each step (like the operation counting table earlier)
• Bar charts — show array elements as bars that swap during sorting
• Tree diagrams — show recursive call structures
• Animated simulations — interactive programs that let you step through an algorithm

Algorithm Visualization: Sorting Comparison MicroSim

Diagram:

Imagine a MicroSim where you can watch three sorting algorithms race side by side. Each algorithm gets the same shuffled array. You can see:

• Selection sort slowly scanning for the minimum, making ( O(n^2) ) comparisons
• Insertion sort building the sorted portion from left to right
• Merge sort splitting, sorting, and merging — finishing much faster

Visualizations like this make the difference between ( O(n^2) ) and ( O(n \log n) ) viscerally obvious. You can see merge sort pulling ahead as the array gets larger.

When you design your own algorithms, try drawing diagrams or building trace tables. If you can't trace your algorithm by hand, you don't fully understand it yet.

Memoization: Remember and Reuse

Now for one of the most satisfying optimization techniques in all of programming. Memoization is a technique where you store the results of expensive function calls and return the cached result when the same inputs occur again.

The classic example is the Fibonacci sequence. Here's the naive recursive version:

def fib(n):
    """Naive recursive Fibonacci. O(2^n) — very slow!"""
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

This looks elegant, but it's horrifically slow. To compute fib(5), it computes fib(4) and fib(3). But to compute fib(4), it also computes fib(3) — the same work, done twice! The number of function calls grows exponentially: ( O(2^n) ). Try fib(40) and you'll be waiting a very long time.

Now watch what happens with memoization:

def fib_memo(n, memo={}):
    """Memoized Fibonacci. O(n) — dramatically faster!"""
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

With memoization, each Fibonacci number is computed exactly once and then stored in the dictionary. Instead of ( O(2^n) ), we get ( O(n) ). That's the difference between "my computer can't do this" and "done in a millisecond."

Let's prove it with empirical analysis:

import time

# Naive version (don't try values much above 35!)
start = time.time()
result = fib(35)
naive_time = time.time() - start

# Memoized version
start = time.time()
result = fib_memo(35)
memo_time = time.time() - start

print(f"fib(35) = {result}")
print(f"Naive:    {naive_time:.4f} seconds")
print(f"Memoized: {memo_time:.8f} seconds")
print(f"Speedup:  {naive_time / memo_time:,.0f}x faster")

Typical output:

fib(35) = 9227465
Naive:    3.2145 seconds
Memoized: 0.00001200 seconds
Speedup:  267,875x faster

Monty says: You've got this!

Over 200,000 times faster from adding a dictionary cache! Memoization is one of those techniques that feels like cheating — but it's completely legit. Any time you see a recursive function recomputing the same values over and over, memoization is your best friend.

Python also provides a built-in decorator for memoization:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

print(fib_cached(100))
# Output: 354224848179261915075 — computed instantly!

The @lru_cache decorator handles all the caching for you. The name stands for "Least Recently Used cache." With maxsize=None, it caches every result without evicting any.

Putting It All Together

Let's see how these concepts connect by solving a problem using multiple approaches.

Problem: Given a list of integers, find the length of the longest subarray where all elements sum to at most a target value.

# Brute force: O(n^3) — check every subarray, sum each one
def longest_subarray_brute(nums, target):
    max_length = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            if sum(nums[i:j+1]) <= target:
                max_length = max(max_length, j - i + 1)
    return max_length

# Sliding window: O(n) — elegant and fast
def longest_subarray_window(nums, target):
    max_length = 0
    window_sum = 0
    left = 0

    for right in range(len(nums)):
        window_sum += nums[right]

        while window_sum > target:
            window_sum -= nums[left]
            left += 1

        max_length = max(max_length, right - left + 1)

    return max_length

# Test both
data = [1, 2, 3, 1, 1, 1, 2, 3]
target = 6
print(longest_subarray_brute(data, target))   # 5
print(longest_subarray_window(data, target))   # 5

The brute force version is ( O(n^3) ) — three layers of work (two loops plus the sum() call). The sliding window version is ( O(n) ) — a 1,000,000,000x improvement at ( n = 1{,}000 ). Same answer, wildly different performance.

Monty says: You've got this!

If this chapter felt intense, take a breath. You just learned tools that many college students struggle with. The key is practice: pick a problem, try brute force first, then see if you can apply a pattern (two pointer, sliding window, frequency counter) or a strategy (divide and conquer, greedy, memoization) to make it faster. Every expert started exactly where you are now.

Key Takeaways

1. Logarithmic time ( O(\log n) ) cuts the problem in half at each step — this is why binary search is so fast.

2. Linearithmic time ( O(n \log n) ) is the best possible for general comparison-based sorting algorithms like merge sort.

3. Always consider best, average, and worst case — an algorithm's performance can vary dramatically depending on the input.

4. Empirical analysis with Python's time module lets you measure real performance and verify your Big-O predictions.

5. Counting operations is the foundation of complexity analysis — trace through your code and count how work scales with input size.

6. Brute force is a valid first approach: get it working correctly, then optimize.

7. Divide and conquer splits problems into smaller independent subproblems — it's the strategy behind merge sort and fast exponentiation.

8. Greedy algorithms make locally optimal choices, but they don't always produce globally optimal results.

9. Algorithm tradeoffs (time vs. space) and efficiency vs. readability are real-world engineering decisions — context matters.

10. The two pointer, sliding window, and frequency counter patterns transform ( O(n^2) ) brute force solutions into ( O(n) ) solutions.

11. Recursion is a powerful tool when combined with strategies like divide and conquer.

12. Memoization caches the results of function calls, turning exponential algorithms into linear ones (like Fibonacci going from ( O(2^n) ) to ( O(n) )).

13. Algorithm visualization through trace tables, diagrams, and simulations builds deep understanding of how algorithms behave.

---

Brute Force vs. Two Pointer: What's the Tradeoff?

You have a sorted list of 10,000 integers and need to find a pair that sums to a target value. Compare the brute force approach (( O(n^2) )) with the two pointer approach (( O(n) )).

(a) How many pair comparisons does the brute force approach make at most?

(b) How many steps does the two pointer approach take at most?

(c) If each comparison takes 1 microsecond, how long does each approach take?

Answer:

(a) Brute force checks ( \frac{n(n-1)}{2} = \frac{10{,}000 \times 9{,}999}{2} = 49{,}995{,}000 ) pairs.

(b) Two pointer takes at most ( n = 10{,}000 ) steps.

(c) Brute force: ( 49{,}995{,}000 \times 1\mu s \approx 50 ) seconds. Two pointer: ( 10{,}000 \times 1\mu s = 0.01 ) seconds. The two pointer approach is about 5,000 times faster — and both give the same correct answer.

Memoization Magic: Why Does It Help?

Consider the naive recursive Fibonacci function.

(a) Draw (or describe) the recursive call tree for fib(6). How many total function calls are made?

(b) With memoization, how many unique computations are needed for fib(6)?

(c) Explain in your own words why memoization changes the complexity from ( O(2^n) ) to ( O(n) ).

Answer:

(a) The call tree for fib(6) makes 25 total calls. fib(3) alone is computed 4 separate times! The tree branches exponentially because each call spawns two more.

(b) With memoization, we compute fib(0), fib(1), fib(2), fib(3), fib(4), fib(5), and fib(6) — exactly 7 unique computations (that's ( n + 1 )).

(c) Without memoization, the function recomputes the same subproblems over and over, leading to an exponential explosion of duplicate work. Memoization stores each result the first time it's computed, so every subsequent call with the same argument returns instantly from the cache. Since there are only ( n + 1 ) unique inputs, the total work is ( O(n) ).

Greedy vs. Optimal: When Does Greedy Fail?

Suppose you have coin denominations of [25, 15, 1] and need to make change for 30 cents.

(a) What solution does the greedy algorithm produce? How many coins?

(b) What is the optimal (fewest coins) solution?

(c) Why does the greedy approach work for standard US coins [25, 10, 5, 1] but fail for [25, 15, 1]?

Answer:

(a) Greedy picks the largest coin first: 25, then five 1s = [25, 1, 1, 1, 1, 1]. That's 6 coins.

(b) The optimal solution is [15, 15] — just 2 coins.

(c) The greedy algorithm works for US coins because of a special mathematical property: each coin denomination is at least twice the next smaller one, so you never need to "un-pick" a large coin. With [25, 15, 1], picking 25 first blocks you from using two 15s. The greedy approach fails when a locally optimal choice prevents the globally optimal solution. For arbitrary coin sets, you need dynamic programming (a topic for a future course!) to guarantee the best answer.