AP CSP 3.17 Exercise 2: Algorithmic Efficiency Applied Challenge

Big Idea 3: Algorithms and Programming · Topic 3.17 · Exercise 2

Algorithmic Efficiency: Applied Challenge

Six comparisons between reasonable and unreasonable running times, using concrete input sizes.

Back to the Topic 3.17 lessonAll Big Idea 3 topics

How this one is different

The exam does not ask for formal notation. It asks whether the work grows in step with the input or explodes past it.

Applied Practice

6 questions · scenario driven · every answer is recorded for your teacher

Question 1 of 6Analyze
Algorithm A examines each of n items once. Algorithm B examines every pair of items.
How does the work compare as n grows?
Incorrect. Both do more work as the input grows.
Incorrect. One pass and every pair grow at clearly different rates.
Correct. Examining every pair means roughly n times n comparisons, so the work scales with the square while a single pass scales directly with n.
Incorrect. Execution order has nothing to do with growth rate.
Question 2 of 6Apply
Which describes an algorithm that runs in reasonable time?
Incorrect. Reasonable time describes how work scales with input size, not a fixed wall clock target.
Correct. The line the course draws is polynomial growth on one side and exponential or factorial growth on the other.
Incorrect. Loops are unrelated to the classification.
Incorrect. Optimality and running time are separate properties.
Question 3 of 6Evaluate
A problem can be solved exactly only by checking every possible arrangement, and there are 2 to the n arrangements.
What happens as n grows, and what is the standard response?
Correct. When exact solutions are unreachable at scale, a heuristic trades the guarantee of optimality for an answer that arrives.
Incorrect. Undecidable means no algorithm exists at all, which is a different category from slow.
Incorrect. A faster language shifts the constant factor and does nothing about exponential growth.
Incorrect. Exponential growth is the definition of not remaining practical.
Question 4 of 6Transfer
A delivery company needs a good route through 40 cities.
Which characterization is correct?
Incorrect. No linear time exact solution is known.
Incorrect. It is modeled by computers constantly, which is why heuristics for it are well studied.
Incorrect. Routes are findable. The optimal one is merely expensive to prove.
Correct. This is the standard example of a problem where exact optimization scales badly and heuristics are used instead.
Question 5 of 6Apply
An algorithm takes 2 seconds on 1,000 items and 4 seconds on 2,000 items. What growth does this suggest?
Incorrect. Logarithmic growth would add only a small increment rather than doubling.
Incorrect. Exponential growth on a doubled input would be far more than double the time.
Correct. Time scaling in proportion to input size is what linear growth means.
Incorrect. Constant time would show the same duration for both sizes.
Question 6 of 6Evaluate
A student says a heuristic gives the wrong answer, so it should never be used.
What is the correct response?
Incorrect. An exact answer that never finishes solves nothing.
Correct. The tradeoff is deliberate: give up the guarantee of optimality to get a usable answer within a practical amount of time.
Incorrect. They sometimes do, but without any guarantee, which is the whole distinction.
Incorrect. Heuristics apply to problems that are decidable but expensive. Undecidable problems have no algorithm at all.

Where to go next

Rework the Topic 3.17 lesson and quiz Sit the Big Idea 3 unit test part A Sit the Big Idea 3 unit test part B

Get in Touch

Whether you're a student, parent, or teacher — I'd love to hear from you.

Just want free AP CS resources?

Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.

Typically responds within 24 hours
✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

✉

Email

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]