3.17 Algorithmic Efficiency
Compare ways to find books and see how algorithmic work grows with a library catalog.
1. 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.
2. LxD Cycle Process
Empathize: A librarian wants to find a book quickly, even when the catalog has thousands of entries.
Define · POV and goal: Beginners need to compare correct solutions by their work, not their code length. Count checks, explain growth, and identify the conditions a method needs.
Ideate · HMW: How might we find the same book while inspecting fewer entries? Compare checking one at a time with repeatedly halving a sorted catalog.
Prototype & Test: At each stop, predict → run → change → explain. Have a peer recommend a search for a large sorted catalog, then reconsider an unsorted one. Revise one confusing explanation and test it again.
3. 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 (1 minute)
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.
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 (2 minutes)
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.
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.
4. 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.
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.
5. Hacks & Practice Tasks
Create your homework page
- In your portfolio repository, create
navigation/homework/3-17.md. - Paste this frontmatter, replacing
your-github-id:
---
layout: post
title: Library 3.17 Algorithmic Efficiency Homework
author: your-github-id
permalink: /homework/3-17/
---
- Add
## Popcorn,## MCQ,## Homework,## Tests, and## Design Thinking. Copy checkpoint B and adapt Example C. Record work like this:
```python
# 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. Verify your published
/homework/3-17/URL, then submit through your teacher’s usual assignment channel. IncludeMCQ 3.17: __/4 | answers: __,__,__,__.
Submission rules: Start each test fresh, identify the language, include actual output, and check that the published link opens.
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.
6. Grading Plan (1 Point Total)
| Part | Points | Evidence |
|---|---|---|
| Popcorn | 0.2 | Prediction, edited calculator, output, and search recommendation. |
| MCQ | 0.2 | 0.05 per correct answer; record answers and score. |
| Homework | 0.3 | Correct main/doubled counts and a justified library recommendation. |
| Tests | 0.2 | Main/empty outputs and a specific growth explanation. |
| Design thinking | 0.1 | Librarian need, choices, prototype, and actual test/revision. |
Quick validation: All sections present; 12/12/144 and empty/0 verified; doubling and search explanations included; published link opens.
7. Lesson Revisions & Feedback Evidence
- Feedback received: Use the data-abstractions lesson’s structure and teaching flow for algorithmic efficiency.
- Revision made: Added a library intro card, seven-stage structure, warm-up, graded checkpoint, reference tables, paired Python/Pseudocode starters, and revealable debriefs.
- Scope: Changes stay in this notebook; the existing browser-based Python runner remains available.
- Peer playtest: Pending. Record reviewer → confusion → revision → actual retest result. Do not invent feedback.
References
- College Board. (2023). AP Computer Science Principles course and exam description, Topic 3.17, printed pp. 94–95, AAP-4.A.3–9. Official reading.
- Open Coding Society. (n.d.). 3.02 Data Abstractions. Lesson layout and activity-flow reference. Adapted here for books and algorithmic efficiency.
Submit: Published homework URL, Popcorn evidence, MCQ answers/score, required tests, recommendation, and your design-thinking note.
linear_checks ← 5 // Checks to reach book 15 from the beginning. binary_checks ← 3 // Checks to reach book 15 by halving the catalog. DISPLAY(linear_checks) // Show linear checks. DISPLAY(binary_checks) // Show binary checks. DISPLAY(linear_checks - binary_checks) // Show checks saved. n ← 8 // Set the catalog size to a nonnegative whole number. linear_checks ← n // Linear search can inspect every entry. remaining ← n // Begin with the full search area. binary_checks ← 0 // An empty catalog needs no checks. REPEAT UNTIL(remaining = 0) // Count worst-case halvings using the supplied helper. { binary_checks ← binary_checks + 1 // Inspect one middle entry. remaining ← (remaining - (remaining MOD 2)) / 2 // Keep the larger remaining half, rounded down. } DISPLAY(n) // Show the number of books. DISPLAY(linear_checks) // Show linear worst-case checks. DISPLAY(binary_checks) // Show binary worst-case checks. n ← 10 // Set the number of books. visits ← n // Model one visit for each book. pairs ← n * n // Model every ordered pair, including self-pairs. DISPLAY(n) // Show the input size. DISPLAY(visits) // Show linear work. DISPLAY(pairs) // Show quadratic work.