C++ complexity of algorithm?

Admin 1
Viewed 98

I wrote the following code:

class Solution {
public:
    int countPrimes(int n) {
        if (n==0 || n==1)
            return 0;
        int counter=n-2;
        vector<bool> res(n,true);
        for (int i=2;i<=sqrt(n)+1;++i)
        {
            if (res[i]==false)
                continue;
            for (int j=i*i;j<n;j+=i)
            {
                if (res[j]==true)
                {
                    --counter;
                    res[j]=false;
                }
            }
        }
        return counter;
    }
};

but couldn't find its complexity, the inner loop according to my calculations runs n/2 + n/3 + ... + n/sqrt(n)

big-o algorithm c++
2 Answers

Ok, let try to get the sum from your formula first (I am going to use your convention naming the variables):

enter image description here

Now, please note that n is a constant in the sum, so it can be moved outside the summary.

enter image description here

Now, we have one part which is linear and one part that we still need to estimate, but if you look closely it is very similar to the harmonic series, indeed for n that goes to infinity is the harmonic series - 1.

The grow rate of it is well know ln(n) + 1.(https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

So, complexity of the algorithm is n*ln(n).

Update

The Beta answer has the correct result (using the correct starting point), I will leave the above answer because the procedure remain the same and the answer, IMHO, it is still useful.

user_5081750

"...The inner loop according to my calculations runs n/2 + n/3 + ... + n/sqrt(n)"

Ah, be careful with that ellipsis. It actually runs

n/2 + n/3 + n/5 + n/7 + n/11 + ... + n/sqrt(n)

This is not n times the harmonic series, this is n times the sum of the reciprocals of the primes, a sum which grows as log(log(greatest denominator)).

So the complexity of the algorithm is O(n log log(n)).

user_1289400
Related