The Hidden O(N log N): Harmonic Series in Algorithms

Quick Revisit

• USE WHEN: loop iterates over multiples: for i in 1..n: for j = i, 2i, 3i, ..., n
• INVARIANT: total iterations = n/1 + n/2 + ... + n/n = n·H(n) = O(n log n), not O(n²)
• TIME: O(n log n) | SPACE: O(n)
• CLASSIC BUG: assuming the nested loop is O(n²) and rejecting a correct O(n log n) solution
• PRACTICE: 08-ladder-mixed

You see a loop: for i in 1..n: for j in i, 2i, 3i, ..., n. Your instinct says $O(n^2)$. But count the iterations: $n/1+n/2+n/3+\cdots +n/n=n\times H(n)\approx n\ln n$. That's $O(n\log n)$.

Difficulty: [Intermediate]CF Rating Range: 1400-1900 Prerequisites: Number Theory, Problem Pattern Recognition

Contents

• The Harmonic Number
• Five Patterns Where It Appears
• Visual: How the Sum Grows
• The Trap: Nested != Quadratic
• Practice Problems

---

The Harmonic Number

The $n$-th harmonic number is defined as:

$$H(n)=\sum _{k=1}^n\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$$

It grows as $\ln n+\gamma$ where $\gamma \approx 0.5772$ is the Euler-Mascheroni constant. For competitive programming, the only fact you need is $H(n)=\mathrm{\Theta }(\log n)$.

When a loop iterates over multiples of $i$ for all $i=1\dots n$, the total work is:

$$\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor =n\cdot H(n)=\mathrm{\Theta }(n\log n)$$

This single identity explains the complexity of a surprising number of algorithms.

Five Patterns Where It Appears

1. Sieve of Eratosthenes

The classic prime sieve marks composites by iterating over multiples of each prime:

for (int i = 2; i <= n; i++) {
    if (!is_composite[i]) {           // i is prime
        for (int j = 2 * i; j <= n; j += i)
            is_composite[j] = true;   // mark multiples
    }
}

The outer loop runs for every prime $p\le n$. The inner loop for prime $p$ does $n/p$ work. Total: $\sum _{p\text{ prime}}n/p\approx n\ln \ln n$ by Mertens' theorem -- even better than $O(n\log n)$ because we skip non-primes.

But the argument generalizes: if the outer loop ran for all $i$, not just primes, it would be $n\cdot H(n)=O(n\log n)$.

2. Counting Divisors of All Numbers 1..n

"For every $i$ from 1 to $n$, add 1 to d[j] for every multiple $j$ of $i$."

vector<int> d(n + 1, 0);
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        d[j]++;

Inner loop for $i$: exactly $\lfloor n/i\rfloor$ iterations. Total: $\sum _{i=1}^n\lfloor n/i\rfloor =\mathrm{\Theta }(n\log n)$.

After this loop, d[j] holds the number of divisors of $j$. Simple, fast, and the harmonic argument is the proof.

3. "For Each Value v, Process All Multiples of v in the Array"

This is where the harmonic argument actually shows up. For each value $v$, walk every multiple $v,2v,3v,\dots$ up to the maximum value:

for (int v = 1; v <= max_val; v++)
    for (int m = v; m <= max_val; m += v)
        if (cnt[m] > 0) /* process elements equal to m */;

Inner loop for $v$: $\lfloor \text{max\_val}/v\rfloor$ steps. Total $\sum _v\text{max\_val}/v=\mathrm{\Theta }(\text{max\_val}\cdot \log \text{max\_val})$. This pattern arises in GCD/LCM problems where you ask "which elements are divisible by $v$?" or "which elements share a divisor with $v$?"

Contrast — the linear lookalike. Grouping elements by their exact value (by_val[a[i]].push_back(i) and then iterating over each by_val[v] once) is not harmonic — it's linear. Each element is visited once. The harmonic sum only appears when the inner loop steps through multiples; it is easy to mis-label a linear bucket pass as harmonic.

4. GCD-Based Problems: Iterate Over Possible GCD Values

"Count pairs $(i,j)$ with $gcd(a_i,a_j)=g$." A standard approach: for each candidate $g$, collect all elements divisible by $g$, then count pairs among them.

for (int g = 1; g <= max_val; g++) {
    // collect indices where a[i] % g == 0
    for (int m = g; m <= max_val; m += g)
        if (cnt[m] > 0) /* add cnt[m] to group */;
    // count pairs in the group
}

The nested loop is our familiar $\sum _{g=1}^{M}M/g=O(M\log M)$ where $M$ is the maximum value. Combined with Möbius inversion, this solves many "count by GCD" problems efficiently.

5. Contribution by Divisor: "Sum of d(i) for i=1..n"

"Compute $\sum _{i=1}^n{\sigma }_0(i)$" -- the total number of divisors across $1$ to $n$. Flip the sum: instead of iterating over $i$ and counting its divisors, iterate over each divisor $d$ and count how many multiples of $d$ lie in $[1,n]$:

$$\sum _{i=1}^n{\sigma }_0(i)=\sum _{d=1}^n\lfloor \frac{n}{d}\rfloor$$

This is exactly $n\cdot H(n)$. No factoring needed -- a clean $O(n)$ scan if you precomputed the sieve, or an $O(\sqrt{n})$ computation using the Dirichlet hyperbola method.

The same "swap the order of summation" trick applies to $\sum {\sigma }_1(i)$ (sum of divisors), $\sum \varphi (i)$ (Euler's totient), and similar multiplicative functions.

Visual: How the Sum Grows

n        H(n)       n*H(n)       n²
──────────────────────────────────────────
10       2.93          29         100
100      5.19         519       10000
1000     7.49        7490     1000000
10000    9.79       97876    10^8
100000  12.09     1209015    10^10    <- n*H(n) fits in time; n² does not

The gap between $n\log n$ and $n^2$ widens fast. At $n={10}^5$, the ratio is roughly $8000\times$. That's the difference between AC and TLE.

The Trap: Nested != Quadratic

The most common mistake when analyzing harmonic-style loops:

"I see two nested for loops, so it must be $O(n^2)$."

Not all nested loops are quadratic. The key is how the inner loop's range depends on the outer variable. If the inner loop iterates over multiples (step size = $i$), the total work is harmonic. If the inner loop always runs $n$ times regardless of $i$, then it's quadratic.

Rule of thumb: if the inner loop looks like for (j = i; j <= n; j += i), suspect $O(n\log n)$, not $O(n^2)$. Write out the sum and verify.

This insight extends beyond number theory. Any algorithm where you "for each bucket of size $s$, do $n/s$ work" and the bucket sizes cover $1\dots n$ yields harmonic total work. Sorting algorithms like patience sort and some cache-oblivious strategies rely on exactly this.

Practice Problems

Problem	Key Idea	Source
CF 236B -- Easy Number Challenge	Sieve-style divisor counting	CF
CF 1154G -- Minimum Possible LCM	Iterate multiples to find pairs sharing a divisor	CF
CF 1033D -- Divisors	Counting divisors via prime factorization and harmonic analysis	CF
CF 1175E -- Minimal Segment Cover	Sparse table over intervals with harmonic structure	CF
SPOJ DIVSUM -- Divisor Summation	Sum of proper divisors; contribution trick	SPOJ

---

See also: Number Theory for the deeper theory of multiplicative functions and Möbius inversion. The harmonic argument is the bread-and-butter complexity tool for all of them.