Complexity Analysis

In this lesson, we'll see the run-time analysis for Sieve.

The outer loop

for (int i = 2; i * i <= N; i++)

Runs for N\sqrt{N} values but the number of iterations of the inner loop is dependent on ii.

for (int j = i + i; j <= N; j += i)

Also, note that the inner loop only runs for values when ii is prime.

ii Inner loop iterations
2 N2\frac{N}{2}
3 N3\frac{N}{3}
4 00
5 N5\frac{N}{5}
6 00
7 N7\frac{N}{7}
8 00

Total number of operations:

N2+N3+N5+N7+...\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \frac{N}{7} + ...

=N[12+13+15+17+...]= N[\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + ...]

The growth of the sum of the reciprocals of primes is O(log(logN))O(log(logN)). The proof is beyond the scope of this lesson but folks who would like to know more can go here.

This gives us the total time complexity of Sieve of Eratosthenes - O(Nlog(logN))O(N*log(logN)).


In the next lesson, we’ll see a variation of Sieve for a higher range of integers.

Get hands-on with 1200+ tech skills courses.