Counting Statement Executions

A single loop that runs n times executes its body n times — that part feels instant because the count grows in a straight line with n. Nest a second loop inside it, and the inner loop restarts from scratch on every single pass of the outer loop. If the inner loop also runs n times, the body inside it runs n times for each of the n outer passes, so the total is n times n, or n^2. That squaring is why the same data that flew through one loop crawls through two: double n and a single loop takes twice as long, but a nested loop takes four times as long, because both the rows and the columns of work double.

To count executions without running anything, look at each loop level separately. Ask how many values the loop variable takes, write that as an expression in terms of n (or in terms of the outer variable, if the inner bound depends on it), then multiply or sum across the outer loop's passes. When the inner loop's starting or stopping point shifts with the outer variable — j starting at i+1, say — the inner loop doesn't run the same number of times on every pass, so you sum a shrinking (or growing) count over all outer values instead of just multiplying two fixed numbers.

This is the algebraic partner to tracing: a trace table shows you the rows filling in one at a time, and counting gives you the formula that predicts how many rows there will be before you trace a single one. It sets up later reasoning about how runtime scales, since n² and n(n-1)/2 behave the same way as n grows large.