AP CSP Day 56: Algorithm Efficiency - Reasonable Time
Share
Big Idea 3
Day 56 Practice
Focus: Algorithm Efficiency - Reasonable Time
Practice Question
An algorithm's runtime doubles with each additional input element. For 10 elements it takes 1 second. How long for 20 elements?
Why This Answer?
Doubling with each element is exponential (2^n). Going from 10 to 20 elements means 10 more doublings: 2^10 = 1024× slower ≈ 1000 seconds.
Why Not the Others?
A) This would be linear growth.
B) This underestimates exponential growth.
C) This is only double, not 2^10 times.
Common Mistake
Watch Out!
Not recognizing exponential growth. 'Doubles with each element' means 2^n, which explodes quickly.
AP Exam Tip
Exponential algorithms (2^n) are unreasonable time. Adding 10 inputs = 2^10 = 1024× slower. Infeasible for large inputs.