analyzing nested loops

Nested loops — a loop inside a loop inside a loop — are where most polynomial running times come from, and where most analysis mistakes also come from. The instinct 'two loops means n^2, three means n^3' is a decent first guess but is wrong often enough that you should always check, because the real count depends on how the inner bounds relate to the outer indices.

When the bounds are independent, multiplication is correct: 'for i = 1 to n: for j = 1 to n: O(1)' runs n times n = n^2 inner steps, so Theta(n^2); add a third independent loop and it is Theta(n^3). But when an inner bound depends on the outer index, you must sum, not just multiply. The classic 'for i = 1 to n: for j = i to n' does (n) + (n-1) + ... + 1 = n(n+1)/2 inner steps — still Theta(n^2), but only because the triangular sum happens to be half of n^2; the factor of 1/2 is hidden by Big-O. Where dependence really bites is something like 'for i = 1 to n: for j = 1 to i*i', which sums 1 + 4 + 9 + ... + n^2 = Theta(n^3), not the Theta(n^2) a careless glance might guess.

The reliable procedure: write the total as a nested sum (sum over i of, sum over j of, the inner cost), then evaluate from the inside out using standard series formulas. This converts any nest of loops, however the bounds interlock, into a single closed form whose order you can read off. The honest pitfall is the reflex multiplication: 'k nested loops' is Theta(n^k) only when each loop independently runs Theta(n) times; data-dependent or index-dependent bounds can make the true answer either smaller or, with growing inner bounds, larger.