The test is behind you. Two jobs today: turn it back into learning, and answer the unit’s central question with a real number — how long would this actually take?
Big Idea 3 — Algorithms & ProgrammingDebrief + semester bridge
Before this lesson
No reading. Bring your returned test and something to write with. Everything else is on
this page.
The last day in the Algorithms region — and the last lesson of the semester. One foot is already in Big Data: next semester you’ll run algorithms on real datasets, where “how long will this take?” stops being hypothetical.
2
The Hook
How long would this actually take?
Not “how many steps” — how many seconds. Searching every person on Earth.
Comparing every pair of songs on a streaming service. Trying every subset of 60 items. Some of these take
a blink. One of them takes decades. Before you calculate, guess which.
3
The Idea — a Debrief, Then an Estimate
Part 1: turn the test into learning (15 min)
For every question you missed, write one word next to it:
Label
Means
Fix
count
You knew the idea, miscounted (often the last check)
Redo it on paper, slowly, out loud
concept
You didn’t know why the answer was right
Reopen the lesson from the section 2 table on 4.14
trap
You fell for a distractor you’ve seen before
Write the trap in your own words at the top of your notes
Missed two or more undecidable-vs-unreasonable questions? Redo the
4.13 three-way sort before the final. That’s the most-missed
idea of the semester, and it’s on the final.
Part 2: from steps to seconds
Three moves turn a step count into a real time:
1. Count the steps at real-world size (n = 8 billion? n = 60?). 2. Divide by the computer’s speed — about 1 billion simple steps per
second for a laptop. 3. Convert seconds into something human: minutes, days, years.
Example: comparing every pair among 1 million items is 1,000,000² =
1012 steps. At 109 per second: 1,000 seconds ≈ 17 minutes.
Slow — and still reasonable.
4
Try It — The Wall-Clock Estimator
Pick a problem, set the real-world size, pick a machine. Try making n just a little bigger on the last
two.
problem:
n =
machine:
5
Vocabulary
efficiency Programs
How much work an algorithm does as its input grows. Today: turned into seconds.
reasonable time Programs
Polynomial growth or slower. Can still take minutes — but a faster machine really helps.
unreasonable time Programs
Exponential or factorial growth. A faster machine barely moves the wall.
6
Check
Five estimates. Use 1 billion steps per second unless the question says otherwise.
0 of 5 answered
7
Impact Check
Waiting for faster computers won’t save you
Computers have gotten enormously faster over the decades. For reasonable
algorithms, that’s transformative: a job that took a day now takes seconds. For exponential ones,
a machine 1,000 times faster buys you about ten more items — because 210 ≈
1,000.
And for undecidable problems, no amount of speed helps at all. Knowing which of
the three you’re facing tells you whether to buy hardware, find a heuristic, or change the question.
That’s the whole unit, as a real-world decision.
8
Connections
Came from all of Unit 4 — step counts (4.3–4.6), growth classes (4.7), and the
limits of computing (4.9), turned into wall-clock time.
Next: the semester final — Units 0–4. Reopen 4.13
for the System Check.
Opens Unit 5 — Data. Real datasets with thousands of rows, where an efficient
algorithm is the difference between an answer and a frozen laptop.
Returns on the AP exam — “what happens when the input doubles?” is really
today’s question in disguise.