Informal Runtime Comparison

Part of: Iteration

How Much Work Does a Loop Do? Loop analysis means reasoning about how many times a loop runs and how that count grows as the input gets bigger. You do not need formal big-O notation for AP CSA, you just need to compare loops informally by counting iterations. Single vs Nested Loops - A single loop over n items does about n units of work. - A nested loop over n items inside n items does about n n (that is, n squared) units of work. Why the Difference Matters Doubling the input has very different effects: - A single loop : doubling n roughly doubles the work. - A nested loop : doubling n roughly quadruples the work, because (2n) (2n) = 4 n n. For n = 1000, a single loop does about 1,000 steps while a nested loop does about 1,000,000 steps, a thousand times more. This is why an accidental nested loop can make a program crawl on large inputs. Comparing Two Solutions When two programs solve the same problem, the one with fewer iterations for large n is generally faster. Counting loop steps lets you predict this before running anything: A single-loop solution that does the same job in about n steps would scale far better. Always ask: how does the step count grow as n grows?

Challenge: Count Iterations: Single vs Nested