AdvancedMath for DSAUsed everywhere
n/1 + n/2 + n/3 + … ≈ n ln n
Looping over multiples of every i up to n costs n/1 + n/2 + … ≈ n log n, not n². It's why the sieve and “all divisors” loops are fast.
The idea
1 + 1/2 + 1/3 + … + 1/n (the harmonic series) grows like ln n, about 2.3 × log₁₀ n. So a loop where step i does n/i work costs about n ln n in total.
Typical shape: for i in 1..n, for j in i, 2i, 3i, … ≤ n. It looks nested and quadratic, but each i only visits n/i multiples.
Worked example
Count the divisors of every number up to n = 6
- i = 1 touches 1..6 (6), i = 2 touches 2, 4, 6 (3), i = 3 → 3, 6 (2), i = 4, 5, 6 → 1 each.
- Total 6 + 3 + 2 + 1 + 1 + 1 = 14 steps, close to 6 × (1 + 1/2 + … + 1/6) ≈ 14.7.
- For n = 10⁶ it's about 14 million steps, not 10¹².
In code (Python)
def divisor_counts(n):
count = [0] * (n + 1)
for i in range(1, n + 1):
for multiple in range(i, n + 1, i): # n / i steps
count[multiple] += 1
return count # divisor_counts(6)[6] == 4O(n log n) total.
How to spot it
- Loops over multiples (sieves, divisor sums), or step sizes that grow with the outer index.
Common mistakes
- Rejecting a correct idea because two loops look O(n²).
- Confusing it with 1 + 2 + … + n, which is n²/2.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →