How to calculate T (N) for this prime search algorithm

Question

This algorithm will find all primes below N

var f = function(n){ var primes = [2]; //1 var flag; //1 for(var i=3; i<n; i+=2){ // ( from 3 to n-1 ) / 2 flag = true; //1 var startI = 0; // 1 for(var y=primes[startI]; y<=Math.sqrt(i); y=primes[++startI]){ // ??? if(i%y === 0) // 1 flag = false; // 1 } if(flag) // 1 primes.push(i); // 1 } return primes; // 1 } 

As long as my analysis is done before the first cycle, I'm not sure how to handle the second sum (the one that uses primes.length and Math.sqrt ).

T (n) = 1 + 1 + sum ((1+ 1+? Weird sum ???), from i = 3 to n -1) / 2 + 1 + 1

I understand how to analyze before the second nested loop, I suspect it is around log (N) or something like that, but I would like to know the exact number of iterations.

Questions:

• How can I handle a loop that uses arrays in memory to iterate?
• If it is impossible to get the exact number, how can I get a good approximation?

Any help is appreciated (links to similar cases, books, etc.).

Answer 1

The inner loop repeats through an array of all primes below sqrt(i) . Therefore, you need to calculate the number of elements in this array. In the case of an array of primes, you should use approximations for π(i) , the number of primes below i .

You can approximate them x/ln(x) or (much better) li(x) . More details here .

For analysis, x/ln(x) would be simpler.

In total, you get (provided n = 2k+1 )

  T (n) = T (n-2) + O (sqrt (n) / ((1/2) ⋅ln (n))) = O (Σ i = 1, ..., k 2⋅sqrt (2 ⋅i + 1) / ln (2⋅i + 1))

You get a recursive formula from the inner for loop, which iterates over an array of primes below sqrt(n) (approximately sqrt(n)/( (1/2)⋅ln(n) ) ), and the work you have to do is to go that far represented by T(n-2) .

Perhaps you can simplify this. I do not want to be distracted from you :)

Hint: maybe you can use the integral to get an approximation of the sum. But I think there is no “good” way to write it down.

If you forget about 1/ln(i) -part, you can see T(n) ∈ o(n 3/2 ) and T(n) ∈ ω(n) . Maybe you can do better.

As @vib mentioned, you can get a tighter upper bound O(n 3/2 /ln(n)) . But note that sqrt(n)/ln(n) is only an approximation for the number of primes below sqrt(n) . This way you get the best ratings with the best approximations. Since these approximations do not give the exact value of π(n) , we cannot say that this algorithm works in Θ(n 3/2 /ln(n)) .