How to show that Eratosthenes sieve algorithm has a complexity of O(n log n)

Spactapsula2l

Spactapsula2l

Answered question

2022-09-04

How to show that Eratosthenes sieve algorithm has a complexity of O ( n log n )

Answer & Explanation

Salvador Howard

Salvador Howard

Beginner2022-09-05Added 12 answers

Step 1
The total no. of iterations in the seive algorithm can be approximated as
n + n 2 + n 3 + + 1 = n ( 1 + 1 2 + + 1 n ) .
And ( 1 + 1 2 + + 1 n ) = O ( log n )
The more tighter upper bound is given by the following sum n ( 1 + 1 2 + + 1 p + . . . 1 p ) where p is a prime less than n and p′ is the largest prime less than n. And ( 1 + 1 2 + + 1 p + . . . 1 p ) = O ( log log n )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?