Search code examples
complexity-theoryprimessieve-of-eratosthenes

Sieve of Eratosthenes near complexity approximation

I have tried to give a more precise approximation to Sieve of Eratosthenes.

Elementary operations and weights that I used:

 prime[p]         -> 1 operation
 m = p * p        -> 2 operations
 prime[m] = false -> 1 operation
 m = m + p        -> 2 operations

My proof:

Is my proof correct? I found in the literature that the complexity is O(nlog(log(n))) or O(nlog(log(n))/log(n)).

Solution

  • Yes, that's correct, O(nloglogn)==O(nloglog(sqrt(n))):

    enter image description here