How did thi O(n*log(logn)) came as the comolexity?

namanmittal0007 · June 30, 2020, 1:36am

How the complexity for prime sieve came as nloglogn,
it would be helpful in understanding the concept of time complexity calculation

asaurabh_26 · June 30, 2020, 1:42am

Understanding the n*log(log n) time complexity of Sieve of Eratosthenes

If it is assumed that the time taken to mark a number as composite is constant, then the number of times the loop runs is equal to: $\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + ...... p$
On taking n common from the above equation, the above equation can be rewritten as:
$n*(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + ...... p)$
It can be proved as below with the help of Harmonic Progression of the sum of primes :
$\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + ..... = log(log(n))$
On substituting this in the equation, we get the time complexity as:
$O(n*(log(log(n))))$

i hope this help
if you have more doubts regarding this feel free to ask
if your doubt is resolved mark it as resolved from your doubt section inside your course

asaurabh_26 · July 19, 2020, 3:56pm

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.