C49 · Topic 3.17 · 40 minutes · AAP-4.A
Count operations rather than guess from code length
By the end you can:
- Specify the operation being counted.
- Distinguish consecutive from nested repetitions.
- Predict how operation counts change with input size.
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
Compare algorithms by how the number of operations grows with input size, using a stated operation and case. A single traversal has an operation count proportional to n. A full nested traversal over all n entries for each of n entries performs n² inner-body operations.
Source-code length is not a running-time measure. A short nested loop can do much more work than a longer single traversal. A particular small input may hide the growth difference, and real constants still matter for actual elapsed time.
Worked example
AlgorithmA inspects each of n records once. AlgorithmB compares every record with every record, including itself and both orders.
- n 4:A 4 inspections; B 16 comparisons.
- n 8:A 8; B 64. Doubling n doubles A but quadruples B.
- A different pair algorithm comparing only unordered distinct pairs has n(n−1)/2 comparisons; do not substitute that count for this specified loop.
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: Two loops always mean quadratic time.
Two consecutive traversals take about 2 n operations; only suitable nested loops multiply the counts.
Guided practice
Count DISPLAY executions for two consecutive REPEAT n TIMES loops, and for one REPEAT n TIMES containing another REPEAT n TIMES.
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
A nested loop always runs the inner body exactly 3 times per outer element. Explain its growth.
Exit check
When n triples, how does n² change?
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.