C++ complexity of algorithm?

Question

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)

Small note, does anyone know the name of the algorithm I used? I forgot it — , Feb 21 '21 at 09:19
what is your best guess so far? You need to apply the simplification on your formula and obtain a close formula — Alessandro Teruzzi, Feb 21 '21 at 09:21
Seems like `Sieve of eratosthenes`. This should help in understanding the complexity: https://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm — Kunal Kukreja, Feb 21 '21 at 09:24
Does this answer your question? [Time complexity of Sieve of Eratosthenes algorithm](https://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm) — Kunal Kukreja, Feb 23 '21 at 09:43

Alessandro Teruzzi · Answer 1 · 2021-02-22T07:53:25.620

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

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

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.

score 0 · Answer 2 · answered Feb 21 '21 at 17:52

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

C++ complexity of algorithm?

2 Answers2