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

AbcAeffchen · Accepted Answer · 2015-06-17 21:28:21Z

7

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(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 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 Θ(n^3/2/ln(n)).

edited Jun 17, 2015 at 21:28

answered Apr 27, 2015 at 14:42

AbcAeffchen

15.1k15 gold badges52 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

vib Over a year ago

Obviously the sum is upper bounded by n * sqrt(n) / ln (n) (its largest term), and is O(n^{3/2} / ln n). By restricting the sum to the range n/a <= i <= n for some fixed a>1 you get that T(n) is Omega( n^{3/2} / ln n). So you get a tight asymptotic for T(n)

AbcAeffchen Over a year ago

Thanks, I'll add this to my answer. The problem I have with complexities like O(n^{3/2} / ln n) is, that it is hard to compare to others, since you dividing by something. I tried to avoid this.

rahpuser Over a year ago

Thanks. I don't understand why you did T(n-2) + sqrt(n)/0.5*ln(n), can you elaborate more on that please ?

AbcAeffchen Over a year ago

@rahpuser I added an explanation and I corrected the sum a little bit. The sum was not correct, but in big-O it changes nothing.

AbcAeffchen Over a year ago

@rahpuser To be honest: I never read a book about complexity-theory. Maybe you can learn something from other questions here at SO. Maybe you can find some good reads on the website's of some professors, but I only know some works in german and they are not official published.

|

Collectives™ on Stack Overflow

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

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related