Quiz: Algorithms and Problem-Solving Strategies

Test your understanding before moving on. Target: 70% or higher to proceed confidently.

Section 1: Multiple Choice (1 point each)

1. Which of the following BEST describes Big-O notation?

  • A) The exact number of operations an algorithm performs
  • B) How fast an algorithm runs on a specific computer
  • C) How an algorithm's running time grows as input size increases
  • D) The maximum size of input an algorithm can handle
Answer **C)** How an algorithm's running time grows as input size increases. *Why C:* Big-O describes the growth rate — the *shape* of the curve — not exact counts or speeds. *Why not A:* Big-O drops constants and lower-order terms; it doesn't give exact counts. *Why not B:* Big-O is hardware-independent. *Why not D:* Big-O doesn't describe input limits — any algorithm can handle any size, just slower. *Reference:* Section 17.2

2. What is the Big-O of this code?

for i in range(n):
    for j in range(n):
        print(i, j)
  • A) O(n)
  • B) O(n log n)
  • C) O(n²)
  • D) O(2n)
Answer **C)** O(n²) *Why C:* The outer loop runs n times; for each iteration, the inner loop also runs n times. Total: n × n = n². *Why not A:* That would be a single loop. *Why not B:* Linearithmic complexity involves halving at some point. *Why not D:* O(2n) simplifies to O(n), and this is quadratic, not linear. *Reference:* Section 17.3.4

3. What is the time complexity of accessing an element in a Python list by index (e.g., my_list[5])?

  • A) O(n)
  • B) O(log n)
  • C) O(1)
  • D) O(n²)
Answer **C)** O(1) *Why C:* Python lists are implemented as arrays; accessing by index is a direct memory lookup regardless of list size. *Why not A:* That would mean scanning through the list, which isn't needed for index access. *Reference:* Section 17.3.1

4. Which complexity class describes an algorithm that cuts the problem in half at each step?

  • A) O(1)
  • B) O(n)
  • C) O(log n)
  • D) O(n²)
Answer **C)** O(log n) *Why C:* Halving repeatedly means you need log₂(n) steps to reach 1. Example: binary search. *Why not A:* O(1) does the same work regardless of input size. *Why not B:* O(n) processes every element once. *Why not D:* O(n²) compares every element with every other. *Reference:* Section 17.3.2

5. What is the Big-O of this code?

for i in range(n):
    for j in range(100):
        print(i + j)
  • A) O(n²)
  • B) O(100n)
  • C) O(n)
  • D) O(n + 100)
Answer **C)** O(n) *Why C:* The inner loop runs a constant 100 times regardless of n. Total: 100n = O(n) after dropping the constant. *Why not A:* Both loops would need to depend on n for O(n²). *Why not B:* O(100n) simplifies to O(n) — constants are dropped. *Why not D:* O(n + 100) also simplifies to O(n). *Reference:* Section 17.2.2, Check Your Understanding #1

6. A greedy algorithm:

  • A) Always finds the optimal solution
  • B) Tries every possible solution
  • C) Makes the locally optimal choice at each step
  • D) Splits the problem in half and solves each half
Answer **C)** Makes the locally optimal choice at each step. *Why C:* This is the definition of greedy — always pick the best option available right now. *Why not A:* Greedy only finds the optimal solution for problems with the greedy-choice property. *Why not B:* That's brute force. *Why not D:* That's divide and conquer. *Reference:* Section 17.6

7. Which problem-solving strategy is BEST described as "try every possibility"?

  • A) Greedy
  • B) Divide and conquer
  • C) Dynamic programming
  • D) Brute force
Answer **D)** Brute force. *Why D:* Brute force systematically enumerates all candidates and checks each one. *Why not A:* Greedy picks the locally best option, skipping many possibilities. *Why not B:* Divide and conquer splits the problem, doesn't try every possibility. *Why not C:* Dynamic programming avoids redundant work by storing subproblem solutions. *Reference:* Section 17.5

8. What is the key insight behind divide and conquer?

  • A) Always choose the largest element first
  • B) Break the problem into smaller instances of the same problem
  • C) Try every combination of inputs
  • D) Use a dictionary for fast lookups
Answer **B)** Break the problem into smaller instances of the same problem. *Why B:* Divide and conquer splits a problem into subproblems of the same type, solves them, and combines the results. *Why not A:* That's greedy thinking. *Why not C:* That's brute force. *Why not D:* That's a data structure technique, not a problem-solving strategy. *Reference:* Section 17.7

9. O(n² + n) simplifies to:

  • A) O(n² + n)
  • B) O(n²)
  • C) O(n³)
  • D) O(2n²)
Answer **B)** O(n²) *Why B:* Drop lower-order terms. As n grows, n² dominates n completely. *Why not A:* Big-O always drops lower-order terms. *Why not C/D:* These are different growth rates entirely. *Reference:* Section 17.2.2

10. Which is faster for looking up a value: a Python list or a Python dict?

  • A) List — it's simpler
  • B) Dict — it uses hashing for O(1) average lookup
  • C) They're the same speed
  • D) It depends on the size of the data
Answer **B)** Dict — it uses hashing for O(1) average lookup. *Why B:* Dict lookup is O(1) on average (hash table). List lookup with `in` is O(n) (linear scan). *Why not A:* Simplicity doesn't determine speed; lists require scanning. *Why not C:* They use fundamentally different data structures. *Why not D:* The Big-O difference holds for all sizes, though it's more noticeable for large data. *Reference:* Section 17.3, Spaced Review ([Chapter 9](../../part-03-data/chapter-09-dictionaries-and-sets/index.md))

Section 2: Short Answer (2 points each)

11. Explain why an algorithm that is O(n²) on 100 items might seem "fast enough" but becomes impractical on 100,000 items. Use specific numbers to support your answer.

Answer With 100 items, O(n²) means ~10,000 operations — fast on any modern computer. With 100,000 items, O(n²) means ~10,000,000,000 (10 billion) operations. If each operation takes 1 nanosecond, that's 10 seconds — noticeable. And the problem compounds: 1,000,000 items would mean 10¹² operations (~16 minutes). The quadratic growth makes the algorithm impractical as data scales, even though it appeared fine on small inputs. *Reference:* Section 17.2, Threshold Concept

12. Write the Big-O complexity for each of these operations and briefly explain: - a) Appending to a Python list - b) Inserting at position 0 of a Python list - c) Looking up a key in a dict - d) Checking if an element is in a list using in

Answer - a) **O(1)** amortized — append adds to the end; Python pre-allocates space. - b) **O(n)** — every existing element must shift right by one position. - c) **O(1)** average — hash table lookup. - d) **O(n)** worst case — must scan through the entire list. *Reference:* Sections 17.3.1, 17.3.3, Spaced Review ([Ch 9](../../part-03-data/chapter-09-dictionaries-and-sets/index.md))

13. Give an example of a problem where brute force is the most practical approach. Explain why a more sophisticated algorithm isn't needed.

Answer Finding the best combination of 3 items from a list of 20 (e.g., project selection). C(20, 3) = 1,140 combinations — brute force checks all of them in milliseconds. A more sophisticated algorithm (greedy, dynamic programming) adds implementation complexity without meaningful speed improvement because the input is inherently small. *Reference:* Section 17.5.1

14. Explain the time-space trade-off using the duplicate-detection example from the chapter. Which version is faster? Which uses less memory?

Answer The O(n²) nested-loop version uses O(1) extra space (just loop variables) but is slow. The O(n) set-based version uses O(n) extra space (to store the set of seen elements) but is fast. Trading memory for speed: the set version allocates extra memory to avoid redundant comparisons. For large inputs, the time savings are dramatic (e.g., 7,000x speedup for 10,000 items). *Reference:* Section 17.9.2

Section 3: Code Analysis (3 points each)

15. What is the Big-O of this function? Trace its execution for n = 8.

def halver(n: int) -> None:
    while n >= 1:
        print(n)
        n //= 2
Answer **O(log n)**. The value of n is halved each iteration, so the loop runs log₂(n) + 1 times. Trace for n = 8: - Iteration 1: print 8, n becomes 4 - Iteration 2: print 4, n becomes 2 - Iteration 3: print 2, n becomes 1 - Iteration 4: print 1, n becomes 0 - Loop ends (0 < 1) Output: 8, 4, 2, 1 (4 iterations = log₂(8) + 1) *Reference:* Section 17.3.2

16. What does this function return, and what is its Big-O?

def compute(items: list[int]) -> int:
    total = 0
    for i in range(len(items)):
        for j in range(i):
            total += items[j]
    return total
Answer The function sums all prefix sums: for each position i, it sums all elements before position i and adds that to a running total. For `[3, 1, 4]`: - i=0: inner loop doesn't run (range(0) is empty) - i=1: adds items[0] = 3, total = 3 - i=2: adds items[0] + items[1] = 3 + 1 = 4, total = 7 The Big-O is **O(n²)**: the inner loop runs 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 times. *Reference:* Section 17.4.1

17. Identify the bug in this greedy change-making algorithm and explain when it produces a wrong answer:

def make_change(amount: int) -> list[int]:
    coins = [25, 10, 5, 1]
    result = []
    for coin in coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin
    return result
Answer The algorithm itself is correct *for US denominations* [25, 10, 5, 1]. There's no bug for standard coins. However, if the denomination set were changed (e.g., [25, 10, 1] without nickels, or [1, 3, 4]), greedy might not give the minimum number of coins. For [1, 3, 4] and amount 6: greedy gives [4, 1, 1] (3 coins), but optimal is [3, 3] (2 coins). The "bug" is assuming greedy always works — it only works when the coin system has the greedy-choice property. *Reference:* Section 17.6.2

Section 4: Applied Reasoning (3 points each)

18. You have a sorted list of 1,000,000 names. You need to check whether "Zara" is in the list. Would you use a linear scan O(n) or binary search O(log n)? How many comparisons would each require in the worst case?

Answer Use **binary search** — O(log n). - Linear scan worst case: 1,000,000 comparisons (check every name). - Binary search worst case: log₂(1,000,000) ≈ 20 comparisons. Binary search is ~50,000x fewer comparisons. Since the list is already sorted, binary search's precondition is met. *Reference:* Section 17.3.2

19. A developer writes a function to find common elements between two lists:

def common_elements(list_a, list_b):
    result = []
    for item in list_a:
        if item in list_b:
            result.append(item)
    return result

What is the Big-O if list_a has n elements and list_b has m elements? How could you improve it?

Answer **O(n × m)**: For each of the n elements in list_a, `item in list_b` scans up to m elements. **Improvement:** Convert list_b to a set first: 
set_b = set(list_b)      # O(m)
result = [item for item in list_a if item in set_b]  # O(n)
Total: O(n + m), using O(m) extra space for the set. *Reference:* Sections 17.3.3, 17.9.2

20. You're building a spell-checker. For each word the user types, you need to check if it's in a dictionary of 200,000 words. Which data structure would you choose (list, set, or dict)? What's the Big-O of each check? If the user types a 500-word essay, what's the total Big-O for checking all words?

Answer Use a **set** (or dict if you need additional info per word). - List: Each check is O(n) where n = 200,000. Total for 500 words: O(500 × 200,000) = O(100,000,000). - Set: Each check is O(1) average. Total for 500 words: O(500) = O(1) relative to dictionary size. The set is ~200,000x faster per word. Building the set from the word list is a one-time O(n) cost. *Reference:* Section 17.3, Spaced Review ([Ch 9](../../part-03-data/chapter-09-dictionaries-and-sets/index.md))