3.17 Algorithmic Efficiency

Source lesson: python/algorithmic-efficiency

Learning Objective: Compare correct algorithms by counting their work instead of their code length, explain how that work grows with input size n, and state what binary search needs.

Submission notes

  • MCQ 3.17: 4/4 answers: A,B,B,C
  • Popcorn completion: yes
  • Homework metrics: n = 12 → 12 / 12 / 144, n = 24 → 24 / 24 / 576, n = 0 → 0 / 0 / 0, 1,000 books → 1,000 linear vs 10 binary worst-case checks
  • Language: Python

Popcorn

Checkpoint B: Expand the catalog. I changed only n in the supplied calculator, from 8 to 16.

Prediction: For 8 books, a linear search’s worst case checks all 8. A binary search checks 4, because the search area shrinks 8 → 4 → 2 → 1. For 16 books, linear doubles to 16 and binary goes up by only one, to 5.

# Popcorn: Checkpoint B (n = 16)
import math

n = 16
linear_checks = n
binary_checks = 0 if n == 0 else math.floor(math.log2(n)) + 1
print(n)
print(linear_checks)
print(binary_checks)

16
16
5

Actual output: 16, 16, 5, which matches the prediction (the original n = 8 gives 8, 8, 4).

Explanation: A linear search checks one book at a time, so its worst case is n checks, and doubling the catalog doubles the checks. A binary search throws away half of the remaining books after every check, so doubling the catalog adds only one more halving.

Recommendation: Use a binary search on a sorted catalog. At 16 books it already needs 5 checks instead of 16, and the gap widens as the catalog grows. These are worst-case counts, though. For a book at the front of the catalog, like book 3 in the warm-up, a linear search can still win that one search (1 check vs 3).

MCQ

**MCQ 3.17: 4/4 answers: A,B,B,C**

1. Binary search requires: A a sorted catalog with direct access to entries · B short book titles · C a small catalog Answer: A: halving only works if the entries are in order and you can jump straight to the middle one.

2. Which helps compare two correct searches? A code length only · B work and memory as input grows · C variable names Answer: B: efficiency is about the resources an algorithm uses, not how short its code is.

3. If a quadratic model uses 100 checks at n = 10, what does it use at n = 20? A 200 · B 400 · C 100 Answer: B: 20 × 20 = 400. Doubling n gives four times the work.

4. A short-books-first reading heuristic: A always maximizes enjoyment · B needs no work · C can be useful without guaranteeing the best list Answer: C: it gives a reasonable list quickly, but it can miss the best combination of books.

Homework

Homework Hack: Advise the librarian

I adapted Example C to label its output, so the librarian can read each line without knowing that visits = n and pairs = n * n. Each run changes only n.

Task 1: Main catalog (n = 12)

Prediction: 12 books, 12 visits, 144 ordered pairs.

# Homework Hack: Advise the librarian (adapted Example C, n = 12)
n = 12
visits = n
pairs = n * n

print("Books in catalog:", n)
print("Scan every book (visits):", visits)
print("Compare every pair (ordered pairs):", pairs)

Books in catalog: 12
Scan every book (visits): 12
Compare every pair (ordered pairs): 144

Actual output: 12 / 12 / 144, matching the prediction.

Task 2: Doubled catalog (n = 24)

Prediction: 24 books, 24 visits, 576 ordered pairs.

# Homework Hack: doubled catalog (adapted Example C, n = 24)
n = 24
visits = n
pairs = n * n

print("Books in catalog:", n)
print("Scan every book (visits):", visits)
print("Compare every pair (ordered pairs):", pairs)

Books in catalog: 24
Scan every book (visits): 24
Compare every pair (ordered pairs): 576

Actual output: 24 / 24 / 576, matching the prediction.

Why the growth rates are different

Work n = 12 n = 24 Change
Visits 12 24 ×2 (linear)
Ordered pairs 144 576 ×4 (quadratic)

Visiting adds one step per book, so twice the books means twice the work. Pairing multiplies books by books. Doubling n doubles both factors, so the work grows 2 × 2 = 4 times, because every new book has to be paired with every other book as well as itself.

Task 3: Checkpoint B for 1,000 books

Prediction: Linear search checks all 1,000 in the worst case. For binary search, 2⁹ = 512 ≤ 1,000 < 1,024 = 2¹⁰, so it needs 9 + 1 = 10 checks.

# Checkpoint B calculator for a 1,000-book catalog (labels added)
import math

n = 1000
linear_checks = n
binary_checks = 0 if n == 0 else math.floor(math.log2(n)) + 1

print("Books in catalog:", n)
print("Linear search, worst-case checks:", linear_checks)
print("Binary search, worst-case checks:", binary_checks)

Books in catalog: 1000
Linear search, worst-case checks: 1000
Binary search, worst-case checks: 10

Actual output: 1,000 books, 1,000 linear checks, 10 binary checks.

Recommendation to the librarian: For repeated searches of a catalog that is already sorted, use binary search. Its worst case is 10 checks instead of 1,000, which is 100 times fewer, and that saving applies to every search.

If the catalog is unsorted: binary search can give a wrong answer, because halving might discard the half that holds the book. The catalog would have to be sorted first, and sorting takes more work than a single scan. For one search, linear search is the better choice. Sorting only pays off when many searches share that one-time cost.

If an extra sorted copy has to be stored: searches become fast, but that trades memory for time. The catalog takes up twice the space (2,000 entries instead of 1,000), and every added or removed book has to be updated in both copies. This is worth it when searches are frequent and the storage is available.

Tests

Each test is a fresh run where only n changes. Language: Python.

Test 1: Main (n = 12)

Prediction: 12 / 12 / 144

# Test 1: main catalog (n = 12)
n = 12
visits = n
pairs = n * n

print("Books in catalog:", n)
print("Scan every book (visits):", visits)
print("Compare every pair (ordered pairs):", pairs)

Books in catalog: 12
Scan every book (visits): 12
Compare every pair (ordered pairs): 144

Test 2: Empty catalog (n = 0)

Prediction: 0 / 0 / 0

# Test 2: empty catalog (n = 0)
n = 0
visits = n
pairs = n * n

print("Books in catalog:", n)
print("Scan every book (visits):", visits)
print("Compare every pair (ordered pairs):", pairs)

Books in catalog: 0
Scan every book (visits): 0
Compare every pair (ordered pairs): 0
Test n Expected Actual Pass
Main 12 12 / 12 / 144 12 / 12 / 144 Yes
Empty 0 0 / 0 / 0 0 / 0 / 0 Yes

Growth explanation: From 12 to 24 books, visits double (12 → 24) but pairs quadruple (144 → 576), because each extra book adds one visit but is paired with every book. With 0 books there is nothing to scan or pair, so every count is 0 and neither formula breaks. Checkpoint B needs its 0 if n == 0 guard for that same case, because math.log2(0) raises a ValueError.

Design Thinking

Step Library notes
Need A librarian wants to find a book quickly, even when the catalog has thousands of entries.
Goal Choose a search method by counting checks and seeing how the count grows, not by picking the shortest code. Show the answer in words, so the librarian does not have to read formulas.
Methods considered Linear search (works on any catalog, n checks in the worst case), binary search (needs a sorted catalog, floor(log2 n) + 1 checks), and the costs of sorting first (time) or keeping a sorted copy (memory).
Prototype The supplied checkpoint B and Example C calculators, which print one unlabeled number per line.
Test In the Popcorn runs, the output 16, 16, 5 was correct, but a reader needs the code to know which line is the book count, the linear checks, or the binary checks.
Revision I added plain-language labels (Books in catalog, Scan every book (visits), Linear search, worst-case checks, and so on) to the Homework and Tests runs and reran them at n = 12, 24, 0 and 1,000. The counts did not change, and every line can now be read on its own.