0

I have tried to give a more precise approximation to Sieve of Eratosthenes.

Elementary operations and weights that I used:

 prime[p]         -> 1 operation
 m = p * p        -> 2 operations
 prime[m] = false -> 1 operation
 m = m + p        -> 2 operations

My proof:

Is my proof correct? I found in the literature that the complexity is O(nlog(log(n))) or O(nlog(log(n))/log(n)).

flatronka
  • 1,061
  • 25
  • 51
  • After a few logarithm manipulations you will see that `O(nloglogn)==O(nloglog(sqrt(n)))`. – SomeWittyUsername Mar 26 '13 at 10:42
  • Can you show me? I can't see it right now. – flatronka Mar 26 '13 at 10:51
  • Besides that, your proof seems incorrect: 1. Your internal loop will be executed only if index of outer loop is marked as prime - you disregard this fact. 2. I don't see any relation between your (1) and (4),(5). The sum split should look completely different – SomeWittyUsername Mar 26 '13 at 10:53
  • Thanks for your answer, I think that this is not true O(nloglogn)==O(nloglog(sqrt(n))). 1. Yeah you are all right but I compute an upper bound so that is doesn't matter so much. 2. the n is constant so \sum\frac{n}{p} => n\sum\frac{1}{p}, -\sum\frac{p^2}{p} = -\sump – flatronka Mar 26 '13 at 11:05
  • Agree about the sum split. Please explain how did you get to the result in (4). – SomeWittyUsername Mar 26 '13 at 11:12
  • possible duplicate of [Time complexity of Sieve of Eratosthenes algorithm](http://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm) – Déjà vu Mar 26 '13 at 11:27
  • @ring0 please,it is not a duplicate, my question is that my prove is wrong and if it is wrong why? please remove your close vote! – flatronka Mar 26 '13 at 11:33
  • @icepack I have used this: http://mathworld.wolfram.com/MertensConstant.html – flatronka Mar 26 '13 at 11:33
  • Ok. Your notation is a bit inaccurate - it seems that you're summing all the 1/p up to sqrt(n) while you sum only for prime p's. Regarding the `O(nloglog(sqrt(n)))` I'll post as answer – SomeWittyUsername Mar 26 '13 at 11:55

1 Answers1

2

Yes, that's correct, O(nloglogn)==O(nloglog(sqrt(n))):

enter image description here

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85