3.17 Algorithmic Efficiency
Compare how running time grows, and recognise reasonable versus unreasonable time.
- Reference Guide
- Lesson Plan
- Tech Talk · Start with a book search
- A. Popcorn warm-up · Find the book
- Code Runner Challenge
- B. Popcorn checkpoint · Expand the catalog
- Code Runner Challenge
- Other costs and practical limits
- Code Examples
- C. Apply efficiency reasoning · Compare growth
- Code Runner Challenge
- Hacks & Practice Tasks
Reference Guide
Books and the library: Compare ways to find a book, count the work, and see what changes as the catalog grows.
Search map · The sample catalog
| Method | Check 1 | Check 2 | Check 3 | Check 4 | Check 5 |
|---|---|---|---|---|---|
| Linear, target 15 | 3 | 6 | 9 | 12 | 15 found |
| Binary, target 15 | 12 | 18 | 15 found | — | — |
Key terms
| Term | Meaning | Library connection |
|---|---|---|
| Input size | Amount of data, called n. | Number of catalog entries. |
| Correctness | Producing the right answer. | Find the right book or correctly report it missing. |
| Time efficiency | How the work grows with input. | Count inspected entries. |
| Space efficiency | How memory use grows. | A second catalog copy needs extra storage. |
| Best / worst case | Least / most work at a given size. | First match / missing book in a linear search. |
| Heuristic | Useful approach without a guarantee of the best result. | Choose short books first for a reading-time budget. |
Growth patterns
| Pattern | How work grows | Library example |
|---|---|---|
| Constant | Stays the same. | Read one known catalog position. |
| Logarithmic | Grows slowly through repeated halving. | Worst-case binary search. |
| Linear | Doubling n doubles work. | Worst-case linear search. |
| Quadratic | Doubling n gives four times the work. | Compare every book with every book. |
| Exponential | Each additional item can multiply choices. | Consider every possible selection of books: 2ⁿ choices. |
Python and College Board connections
| Purpose | Python | College Board pseudocode |
|---|---|---|
| Store the number of books | n = 8 |
n ← 8 |
| Model linear-search worst case | linear_checks = n |
linear_checks ← n |
| Model all ordered book pairs | pairs = n * n |
pairs ← n * n |
| Display a count | print(linear_checks) |
DISPLAY(linear_checks) |
| Count items in a catalog | len(catalog) |
LENGTH(catalog) |
The supplied binary-search calculator uses math.floor(math.log2(n)) + 1 for positive n. AP pseudocode has no built-in logarithm in its reference sheet, so its version counts halvings instead. You do not need to memorize or write that helper.
Lesson Plan
Objective: Explain algorithmic efficiency and compare the work required by different correct approaches.
Success criteria: Compare counts fairly, explain how they grow, state binary search’s requirements, and describe a time/memory tradeoff.
Tech Talk · Start with a book search
An algorithm is a set of steps that solves a problem. Efficiency describes the time and memory it needs as its input grows. Here, input size n is the number of books in a digital catalog.
Find book 15 in [3, 6, 9, 12, 15, 18, 21]:
- Linear search: Inspect 3, 6, 9, 12, then 15: 5 checks.
- Binary search: Inspect 12, keep the right half, inspect 18, then 15: 3 checks.
Both give the right answer. Binary search needs entries sorted by book ID and direct access to middle entries. Sorting an unsorted catalog also costs work.
A. Popcorn warm-up · Find the book
Predict: What will the three output lines show: linear checks, binary checks, and checks saved?
Run → change: Run Python, switch to Pseudocode, and compare. Now search for book 3 by hand: linear takes 1 check; binary takes 3. Update both counts in either version. Which method wins this time?
Runner controls · languages, saving and reset
Each runner offers Python and Pseudocode. Switching keeps separate edits; it does not translate them. Save stores the selected version, and Trash restores the Python starter. Python runs in your browser and needs an initial runtime download; Pseudocode uses the existing page runner. The calculators show counts, not timed searches. OCS displays each DISPLAY call on a new line.
Library 3.17 Warm-up - Find the book
linear_checks = 5
binary_checks = 3
print(linear_checks)
print(binary_checks)
print(linear_checks - binary_checks)
Code Runner Challenge
Library 3.17 Warm-up - Find the book
View IPYNB Source
# CODE_RUNNER: Library 3.17 Warm-up - Find the book
linear_checks = 5
binary_checks = 3
print(linear_checks)
print(binary_checks)
print(linear_checks - binary_checks)
Warm-up debrief · reveal after predicting
Both versions display 5, 3, then 2. For book 3, the counts become 1, 3, then -2: binary search uses two more checks for this target. One easy case does not describe every search.
Explain to a partner: Why can both methods be correct but use different amounts of work? This warm-up is practice; the checkpoint below is the graded Popcorn task.
B. Popcorn checkpoint · Expand the catalog
Predict: For 8 books, how many checks might each search need in its worst case?
Run → change: Run both versions, then change n to 16 in either version. Which count doubles? Which increases by one? Record your prediction, edited code, output, and recommendation in your homework’s Popcorn section.
Use a nonnegative whole number for n. This supplied calculator models item inspections; it does not perform a search.
Library 3.17 Popcorn - Expand the catalog
import math
n = 8
linear_checks = n
binary_checks = 0 if n == 0 else math.floor(math.log2(n)) + 1
print(n)
print(linear_checks)
print(binary_checks)
Code Runner Challenge
Library 3.17 Popcorn - Expand the catalog
View IPYNB Source
# CODE_RUNNER: Library 3.17 Popcorn - Expand the catalog
import math
n = 8
linear_checks = n
binary_checks = 0 if n == 0 else math.floor(math.log2(n)) + 1
print(n)
print(linear_checks)
print(binary_checks)
Checkpoint debrief · reveal after predicting
For 8 books, both versions display 8, 8, 4. With 16 books, they display 16, 16, 5. Linear-search worst-case work doubles; binary-search work increases by one.
Other costs and practical limits
A short program is not automatically efficient. Compare correct solutions to the same task using comparable counted operations. Sorting before a search costs time; keeping a sorted copy costs memory.
AP CSP calls polynomial growth or lower reasonable time; exponential and factorial growth are examples of unreasonable time as inputs grow. These categories do not promise that every large input finishes quickly. Formal Big O analysis is outside AP CSP exam scope.
Quick partner check: A librarian wants the most enjoyable reading list within a time budget. Why might choosing short books first help, and what could it miss?
Heuristic debrief
It can produce a useful reading list quickly, but short books are not necessarily the most enjoyable. The heuristic may miss the best combination. Checking every selection of 10 books means 1,024 choices; 20 books means 1,048,576.
Code Examples
C. Apply efficiency reasoning · Compare growth
Predict: The librarian can scan every book or compare every book with every book, including itself and both orders. How many visits and pairs are modeled for 10 books?
Run → change: Try n = 20, then n = 0, changing only n. Explain why doubling n doubles visits but quadruples pairs.
These are different library tasks used to illustrate growth. Pairing cannot be replaced by scanning if pairs are what the task needs.
Library 3.17 - Compare catalog growth
n = 10
visits = n
pairs = n * n
print(n)
print(visits)
print(pairs)
Code Runner Challenge
Library 3.17 - Compare catalog growth
View IPYNB Source
# CODE_RUNNER: Library 3.17 - Compare catalog growth
n = 10
visits = n
pairs = n * n
print(n)
print(visits)
print(pairs)
Both versions output: 10, 10, 100: books → visits → ordered pairs. With 20 books, expect 20, 20, 400; with no books, expect 0, 0, 0.
From College Board:
“Efficiency is an estimation of the amount of computational resources used by an algorithm.”
— College Board (2023), Topic 3.17, AAP-4.A.3, printed p. 94. Read pp. 94–95.
Counting work applies AAP-4.A.5; comparing correct solutions applies AAP-4.A.6. Growth classifications and heuristics connect to AAP-4.A.7–9.
Hacks & Practice Tasks
Your library calculator goes here.
Prediction: ...
Actual output: ...
Explanation: ...
- Run your solution in the lesson or class editor. Markdown code fences display code; they do not execute it. Record both required tests.
- Preview, commit, and push. Include
MCQ 3.17: __/4 | answers: __,__,__,__.
MCQ Check · Librarian decisions
Record A, B, or C for each before revealing the key.
- Binary search requires: A a sorted catalog with direct access to entries · B short book titles · C a small catalog.
- Which helps compare two correct searches? A code length only · B work and memory as input grows · C variable names.
- If a quadratic model uses 100 checks at n = 10, what does it use at n = 20? A 200 · B 400 · C 100.
- A short-books-first reading heuristic: A always maximizes enjoyment · B needs no work · C can be useful without guaranteeing the best list.
MCQ answers and explanations
A, B, B, C. Sorting enables halving; efficiency concerns resources; doubling quadratic input quadruples work; heuristics may miss an optimal solution. Record your actual score out of 4.
Homework Hack · Advise the librarian
- Adapt Example C for
n = 12books. Display the book count, visits, and ordered pairs. Predict before running: expect12,12,144. - Double the catalog to
n = 24: expect24,24,576. Explain the different growth rates. - Test an empty catalog with
n = 0: expect0,0,0. Include the main and empty outputs under Tests. - Use checkpoint B for 1,000 books. Recommend a method for repeated searches of an already sorted catalog using the counts: 1,000 versus 10 worst-case checks. Explain what changes if the catalog is unsorted or you must store an extra sorted copy.
- Add a design-thinking note: librarian need, goal, methods considered, prototype, and one actual test/revision. Use clear output labels so the librarian need not understand the formulas.
Connection to the warm-up: A method with better worst-case growth can still use more checks on a particular target. Separate correctness, individual cases, and growth.