Yes, that's correct, O(nloglogn)==O(nloglog(sqrt(n)))
:
Sieve of Eratosthenes near complexity approximation
-
29-03-2022 - |
Question
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)).
La solution
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow