C50 · Topic 3.17 · 40 minutes · AAP-4.A
Reasonable time and heuristic trade-offs
By the end you can:
- Classify polynomial, exponential and factorial growth.
- Explain limits of the reasonable-time convention.
- Justify a heuristic without claiming optimality.
Before this lesson: topics 3.8, 3.9, 3.11.
- Input size
- A measure such as the number of entries to process.
- Reasonable time
- In AP CSP, an algorithm with polynomial running time in the input size.
Understand
AP CSP describes polynomial-time algorithms as running in reasonable time and exponential/factorial algorithms as not running in reasonable time as input size grows. This classification is about growth, not a promise that every polynomial algorithm is fast on every device.
Some problems have no known efficient exact algorithm. A heuristic can find a useful, nonoptimal answer in a practical amount of time, but does not guarantee the best result. Do not confuse inefficient with undecidable: an exhaustive algorithm can always finish for each finite input yet become impractical.
Worked example
A route planner evaluates every ordering of n distinct stops; the number of orderings is n!. A heuristic repeatedly chooses the nearest unvisited stop.
- 4 stops:24 orderings;8 stops:40,320 orderings.
- Exhaustive evaluation can find the best route under the cost model but grows rapidly.
- Nearest-next may be useful sooner but can miss a better overall route; local choices do not certify a global optimum.
Explore each concept
Choose a concept, change its inputs and follow the explanation. Each example models the stated rule or scenario; completing it is practice rather than evidence of mastery.
- Consecutive versus nested loops
- Polynomial, exponential and factorial growth
- Decision versus optimisation
- Heuristic limits
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input size (1–8)4Waiting
- ExploreconsecutiveWaiting
Ready to explore: Loop work, factorial growth and heuristics
Why: Change an input, predict the first effect, then advance one step.
Try this: Change one input or choose another listed case. Predict the effect, reset and compare the states and governing rule.
Step through and experiment
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input 18Waiting
Ready to experiment
Why: Predict the first change, then advance one step.
Try this: Compare n=4, 8 and 16. Read exact labels when a small bar becomes hard to see.
Check a misconception
Claim: If exhaustive search is too slow, no algorithm can ever solve the problem.
An algorithm can be finite but impractical. Undecidability is the absence of any correct algorithm for all allowed instances.
Guided practice
Classify counts n³ and 2ⁿ using the AP reasonable-time convention. State one limit of that classification.
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
A delivery app must return a route within seconds and can accept a near-best route. Explain when a heuristic is appropriate and what it cannot promise.
Exit check
Does measuring one fast run establish polynomial growth?
Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.
Check yourself
Your practice so far
Check an answer to see its rationale.