Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
@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 at 22:46
you need an upper bound so you can relax the conditions. – Mohan Feb 28 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 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 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 at 2:37

1 Answer

up vote 5 down vote

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)$

share|improve this answer
2  
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 at 2:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.