Skip to interview prep
Apexed

63. Why does a loop where the inner index steps by i (for j = i; j <= n; j += i) inside an outer loop i = 1..n run in O(n log n)?

MediumAlgorithm analysis

Technical
Show model answer

For a fixed i the inner loop runs about n/i times. Summing over i gives n(1 + 1/2 + 1/3 + ... + 1/n) = n·H(n), and the harmonic number H(n) grows like ln n. So the total is Θ(n log n).

This pattern appears in the sieve of Eratosthenes (which is actually tighter, O(n log log n), because it only steps by primes) and when enumerating all divisors or multiples of every number up to n.

Why does a loop where the inner index steps by i (for j = i; j <= n; j += i) inside an outer loop i = 1..n run in O(n log n) — Data structures & algorithms inte