counting loop iterations

The running time of most simple algorithms comes down to one question: how many times does each loop body run? Counting loop iterations is the bread-and-butter skill of analysis. The trick is to figure out, as a function of the input size n, the total number of times the inner work happens, then multiply by the cost of that work.

Start with the easy cases. A loop 'for i from 1 to n' runs its body exactly n times, so if the body is O(1) the loop is Theta(n). A loop that halves a counter each pass — 'while n > 1: n = n / 2' — runs about log2(n) times, because you can only halve n down to 1 about log2(n) times; that gives Theta(log n), the hallmark of binary search and similar. The interesting case is when the bound moves: in 'for i from 1 to n: for j from 1 to i', the inner body runs i times on the i-th outer pass, so the total is 1 + 2 + ... + n. Here you cannot just say 'n iterations of n work'; you must sum the arithmetic series, getting n(n+1)/2 = Theta(n^2). Recognizing such triangular sums is the single most common subtlety.

So the method is: write the count as a sum over the loop variable, evaluate the sum in closed form (a few standard ones suffice — the sum from 1 to n is n(n+1)/2, the sum of a halving sequence is about log n, the sum of a geometric series is dominated by its largest term), and that closed form is your iteration count. A common mistake is to glance at two nested loops and reflexively write n^2 without checking whether the inner bound actually depends on the outer index or on the data; sometimes it is far less, sometimes the loop variable jumps by more than one each step.