C / LOOPS AND JUMPS
Nested loops and their quadratic cost
Count how many times a nested loop's inner body runs, recognize when that count grows like n squared, and predict the cost as n grows.
What you will learn
- Multiply the loops' trip counts to get the number of inner-body executions.
- Recognize a j = i + 1 nest as n(n-1)/2 passes, which still grows like n squared.
- Predict that doubling n multiplies a quadratic nest's work by roughly four.
- Spot hidden nesting: a strlen or search call inside a loop adds another factor of n.
Understanding Nested loops and their quadratic cost
Nesting one loop inside another does not add their work, it multiplies it. Each pass of the outer loop starts the inner loop from scratch: the inner header's initialization runs again, so its counter is reset, and the inner loop then runs to completion before the outer loop advances. If the outer loop makes p passes and the inner one makes q passes each time, the innermost statement executes p*q times, while a statement written between the two loops executes only p times.
The interesting case is when both bounds come from the same n. Then the product is n*n, or, for the triangular form where j starts at i + 1, it is n(n-1)/2, which is the sum 0 + 1 + ... + (n-1). The one-half is a constant factor, not a change of shape: in both forms, doubling n multiplies the inner passes by about four and multiplying n by ten multiplies them by about a hundred. That ratio, not the exact count, is what quadratic cost means in practice.
So when you read a nest, look at the innermost statement first, because that is the line whose cost gets multiplied. One division there means n*n divisions; a call that itself loops over n items turns n*n passes into n*n*n character or element comparisons, because the callee's loop is nested inside yours whether or not you can see its braces. Concretely, an n-squared nest at n = 1000 is a million passes and finishes instantly, while the same code at n = 200000 is 4*10^10 passes and will not finish while you wait.
Depth alone tells you nothing; the bounds do. Two nested loops whose limits grow with the same n are quadratic, but a nest over two unrelated sizes costs n*m, and an inner loop with a fixed bound of 3 leaves the whole nest linear.
<stdio.h>
/* Returns how many times the innermost statement ran for this n. */
static long inner_passes(int n)
{
long body = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
body++; /* the multiplied work */
return body;
}
int main(void)
{
for (int n = 4; n <= 32; n *= 2)
printf("n = %2d inner body runs %4ld times n*n = %4d\n",
n, inner_passes(n), n * n);
return 0;
}
Nested loops multiply their trip counts, so the innermost statement's cost is what decides how the program scales with n.
Worked examples
Where the row work belongs
Shows the inner counter restarting each outer pass, and that a statement between the loops runs once per row instead of once per cell.
<stdio.h>
int main(void)
{
int cells = 0;
for (int row = 1; row <= 3; row++) {
for (int col = 1; col <= 4; col++) {
printf("%3d", row * col);
cells++;
}
putchar('\n'); /* outer body: once per row */
}
printf("cells = %d\n", cells);
return 0;
}
Example explained
Line 1The inner header re-runs its initialization on every outer pass, so col starts at 1 again for each row.
Line 2putchar('\n') is in the outer body after the inner loop, so it runs 3 times and produces 3 lines, not 12.
Line 3cells ends at 12 = 3 * 4: the trip counts multiply; they do not add to 7.
Line 4Moving putchar next to cells++ would print one number per line, which is how a misplaced statement announces itself.
Nesting you cannot see
A single visible loop becomes quadratic because the length call in its condition loops over the string every pass.
<stdio.h>
static long scanned = 0; /* characters my_strlen has looked at */
static size_t my_strlen(const char *s)
{
size_t n = 0;
while (s[n] != '\0') {
scanned++;
n++;
}
return n;
}
int main(void)
{
const char *s = "quadratic"; /* 9 characters */
for (size_t i = 0; i < my_strlen(s); i++) {
/* body does no work at all */
}
printf("call in the condition: %ld chars scanned\n", scanned);
scanned = 0;
size_t len = my_strlen(s);
for (size_t i = 0; i < len; i++) {
/* same empty body */
}
printf("length hoisted out: %ld chars scanned\n", scanned);
return 0;
}
Example explained
Line 1my_strlen walks to the terminator, so every call charges 9 character reads to scanned.
Line 2The condition i < my_strlen(s) is evaluated before each of the 9 passes and once more to fail, so the call happens 10 times: 10 * 9 = 90.
Line 3Storing the length in len first makes the scan happen once; the loop body is identical and the total drops from 90 to 9.
Line 4No braces in main are nested, yet the while loop inside my_strlen runs inside the for by virtue of being called from its condition.
Important notes
The product counts inner-body executions only. The inner condition is tested one extra time per outer pass, so an n-by-n nest evaluates it n(n+1) times; that never changes the growth, but it explains a count that is off by n.
Quadratic cost comes from the bounds, not the indentation: an inner loop with a fixed limit is linear no matter how deeply it sits, and unrelated limits give n*m.
Common mistakes
Reusing the outer counter in the inner header, usually a copy-pasted for line where i was never renamed to j: the inner loop leaves i at the bound, the outer increment pushes it past, and the nest makes a single outer pass, so it does n passes instead of n*n with no compiler warning.
Writing the per-row finishing work inside the inner loop: a putchar('\n') or a sum = 0 placed next to the inner body runs once per cell instead of once per row, so a 3-by-4 grid prints as 12 lines and running totals restart mid-row.
Reading n(n-1)/2 as half the work and therefore nearly linear: the half is a constant factor, and a 60000-element pair scan is about 1.8 billion inner passes, which costs seconds even with a trivial body.
Try it yourself
Change, predict, then run
Take the pair loop from the main example, set n = 5, and print i and j inside the inner body; check that the number of printed lines equals 5*4/2. Then change the inner header to start at j = 0 and explain from the new output why the count becomes 25.
Open the C workspaceCheck your understanding
A nest whose inner body runs n(n-1)/2 times takes 0.5 seconds on 1000 items. Roughly how long should you expect it to take on 4000 items?
- About 2 seconds
- About 8 seconds
- About 16 seconds
- About 32 seconds
Show answer
Quadrupling n multiplies n(n-1)/2 by roughly 16, so 0.5 s becomes about 8 s. The 2-second answer scales time with n itself, which ignores that both loop bounds grow together; the 1/2 is a constant and cancels when you take the ratio of two runs.