How to calculate the T(N) for this primes finder algorithm

Question

This algorithm find all prime numbers 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
}

So far my analysis is done till the first loop, I'm not sure how to handle the second sum ( the one that is using 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 till the second nested loop, I suspect that is around log(N) or something like that, but I would like to know the exact number of iterations..

Questions:

• How can I handle that kind of loop that is using arrays in memory to iterate ?
• If not possible 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 iterates over the array of all primes below sqrt(i). So you have to calculate the number of elements in that array. In the case of an array of primes, you have to use approximations for π(i), the number of primes below i.

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

For analysis the x/ln(x) would be easier.

In total you get (assuming 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 the recursive formula from the inner for loop, that iterates over the array of primes lower than sqrt(n) (approximated by sqrt(n)/( (1/2)⋅ln(n) )), and the work you have to do to come this far, represented by T(n-2).

Maybe you can simplify this more. I don't want to take the fun from you :)

Hint: Maybe you can use an integral to get an approximation of the sum. But I think there is no "nice" way to write it down.

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

As @vib mentioned, you can get a tighter upper bound O(n3/2/ln(n)). But notice that sqrt(n)/ln(n) is only an approximation for the number of primes lower than sqrt(n). Thus you get better bounds with better approximations. Since this approximations do not provide the exact value of π(n), we cannot say that this algorithm runs in Θ(n3/2/ln(n)).