Analysing Iterative Algorithms
Most algorithms are just loops wrapped around a little work. So the whole art of analysing them comes
down to one move: turn the loops into a sum. Each time a statement runs it costs
something; the total running time is that cost added up over every iteration. Master a handful of
summation formulas and you can read the
asymptotic
cost of most iterative code straight off the page.
The recipe never changes. Write the running time as
T(n) \;=\; \sum_{\text{iterations}} (\text{cost of one iteration}),
collapse the sum with a known formula, and drop everything but the dominant term. This page builds the
toolkit and then runs it on real loops.
The summation toolkit
Three sums cover the overwhelming majority of loop analyses. Memorise their closed forms and their
asymptotic size:
- Arithmetic series (a loop whose work grows linearly):
\displaystyle \sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \Theta(n^2). These
are the triangular numbers.
- Geometric series (work that halves or doubles): for
r \ne 1,
\displaystyle \sum_{i=0}^{k} r^i = \frac{r^{k+1}-1}{r-1}. When
r < 1 this is \Theta(1) — bounded by a
constant; the sum is dominated by its largest term.
- Harmonic sum (the i-th step does
1/i of the work):
\displaystyle H_n = \sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + o(1) = \Theta(\log n),
with \gamma \approx 0.577 the Euler–Mascheroni constant.
Notice how much the shape of the per-iteration cost tells you: constant work per iteration of
an n-loop gives \Theta(n); linearly growing work
gives the arithmetic series and \Theta(n^2); geometrically shrinking work
collapses to \Theta(1); and the harmonic pattern gives a surprise
\Theta(\log n).
Nested loops and the triangular sum
The classic pattern is an inner loop whose length depends on the outer index. When the inner
loop runs i times on the i-th outer pass, the
total isn't n \times n — it's the triangular sum.
function countPairs(a: number[]): number {
const n = a.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) { // inner runs n-1, n-2, ..., 1, 0 times
count += (a[i] === a[j]) ? 1 : 0;
}
}
return count;
}
The inner body runs
\sum_{i=0}^{n-1} (n - 1 - i) \;=\; (n-1) + (n-2) + \dots + 1 + 0 \;=\; \frac{n(n-1)}{2} \;=\; \Theta(n^2)
times. Only half the n^2 grid is visited (the upper triangle), yet
halving a quadratic leaves it quadratic — the constant \tfrac12 vanishes in
\Theta. The triangular numbers grow like the area of a triangle of side
n, which is why they land on n^2/2:
Worked example 1 — insertion sort, best vs worst
Insertion sort is the perfect
specimen: the outer loop is fixed, but the inner loop's length depends on the data, so best and worst
case split apart.
function insertionSort(a: number[]): void {
for (let i = 1; i < a.length; i++) {
const key = a[i];
let j = i - 1;
while (j >= 0 && a[j] > key) { // how far back we shift depends on the input
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
On an already-sorted array the while guard fails immediately every time:
the inner loop does \Theta(1) work, and
T_{\text{best}}(n) = \sum_{i=1}^{n-1} \Theta(1) = \Theta(n). On a
reverse-sorted array the key must travel all the way to the front, so the
i-th pass does i shifts, and
T_{\text{worst}}(n) = \sum_{i=1}^{n-1} i = \frac{(n-1)n}{2} = \Theta(n^2).
Same code, same n — the input moves us between a linear and a
quadratic sum. (That best/worst distinction is its own big idea, sharpened on the
best,
worst and average case page.)
Worked example 2 — a loop that halves
Not every loop counts up by one. When the loop variable is multiplied or divided
each pass, the iteration count is logarithmic — because you can only halve n
about \log_2 n times before hitting 1.
function highestPowerSteps(n: number): number {
let steps = 0;
for (let k = n; k > 1; k = Math.floor(k / 2)) { // n -> n/2 -> n/4 -> ... -> 1
steps++;
}
return steps; // ~ log2(n)
}
The values of k are n, n/2, n/4, \dots, 1 — a
geometric sequence of length \lfloor \log_2 n \rfloor + 1, so
T(n) = \Theta(\log n). This is the fingerprint of divide-by-a-constant
loops, and the reason binary search and balanced-tree operations are logarithmic. Contrast it with the
additive loop k += 1, which would run n times: the
update rule, not the loop's syntax, sets the growth.
Each term 1/i shrinks toward zero, so it is tempting to think the sum
settles to a finite limit — but it doesn't; it grows forever, just very slowly. Picture the terms as
the areas of unit-width bars of height 1/i; they sit just above the curve
1/x, whose area from 1 to n
is exactly \int_1^n \frac{1}{x}\,dx = \ln n. So
H_n \approx \ln n. It shows up whenever the i-th
item is examined a 1/i fraction of the time — as in the average cost of
inserting into a hash chain, or the expected comparisons in the analysis of quicksort — turning what
looks like linear work into a tidy \Theta(\log n).
The reflex "two nested loops, therefore \Theta(n^2)" is one of the most
expensive habits in algorithm analysis — sometimes an over-count, sometimes an under-count. You must
always ask how many times the inner body actually runs, summed over the outer loop. If the
inner loop's length shrinks (like the triangular j = i+1 \dots n) you still
get \Theta(n^2) — but if the inner loop halves each outer pass,
the total is \sum_{i} \Theta(\log n) = \Theta(n \log n), not
n^2. Worse, an inner loop whose bound is a different variable
(say m edges, not n vertices) is
\Theta(nm) — collapsing it to n^2 throws away the
real cost. Count the iterations; never count the loops.