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

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?

-
@Sasha When you state the number of iterations in the sieve algorithm I get a bit lost. By iterations what do you mean? ... The way I am looking at it is that every row takes O(n/p) steps, p being prime of course. I am saying a step is either circling a prime at its start or crossing off its multiple as I go down the row of integers [2,3,...,n]. Is this not correct at all? –  Robert Feb 28 '13 at 22:46
you need an upper bound so you can relax the conditions. –  Mohan Feb 28 '13 at 22:55
And yes you're correct a step is either circling a prime at its start or crossing off its multiple as you go down the row of integers. By iterations I mean no. of steps every row takes. –  Mohan Feb 28 '13 at 22:57
Thank you for all the help! One more clarification on your point "you need an upper bound to relax the conditions". Does this just mean that we need the upper bound to relate the steps in the sieve to the harmonic series? Or is there more going on here than I am aware of. –  Robert Feb 28 '13 at 23:10
Yes. As I wrote in my answer a tighter upper bound is $n(1 + \frac{1}{2} + \ldots + \frac{1}{p} + ...\frac{1}{p'})$. But we know that $n(1 + \frac{1}{2} + \ldots + \frac{1}{p} + ...\frac{1}{p'})$ is less than $(n(1 + \frac{1}{2} + \ldots + \frac{1}{n})$. It is easier to get closed form for the second one then the first one. –  Mohan Mar 1 '13 at 2:37

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)$
For added knowledge, both of these aren't merely $O$ but $\Theta$. (But neither lead to a big-$\Theta$ estimate on the algorithms running time) –  Hurkyl Mar 1 '13 at 2:42