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

Question

I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem?

Answer 1

Hint: The total no. of iterations in the seive algorithm can be approximated as $n+n/2+n/3+ \ldots +1= n(1 + \frac{1}{2} + \ldots + \frac{1}{n})$. And $(1 + \frac{1}{2} + \ldots + \frac{1}{n})=O(\log n)$

The more tighter upper bound is given by the following sum $n(1 + \frac{1}{2} + \ldots + \frac{1}{p} + ...\frac{1}{p'})$ where $p$ is a prime less than $n$ and $p'$ is the largest prime less than n. And $(1 + \frac{1}{2} + \ldots + \frac{1}{p} + ...\frac{1}{p'})= O(\log \log n)$