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.