Time complexity of an algorithm that finds prime numbers given a vector

Question

I am trying to find the time complexity of the following algorithm that finds the prime numbers given the vector. Specifically I am not sure about the last for loop with another loop nested in it. I think it's O(sqrt(n)/2), and then the loop inside it is O(n)?

void PrimeFind (std::vector<bool> &vec)
{
  int vsize = vec.size();
  size_t sqvsize = ceil(sqrt(vsize));

  std::fill(vec.begin(), vec.end(), true);
  vec[0] = false;
  vec[1] = false;

  for (int i = 4; i < vsize; i += 2)
  {
    vec[i] = false;
  }

  for (int i = 3; i < sqrtvsize; i += 2)
  {
    if (vec[i])
    {
      for (int j = i * i; j < vsize; j += i)
      {
        vec[j] = false;
      }
    }
  }
}

related/dupe: https://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm — NathanOliver, May 28 '19 at 20:37
This looks like https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, you can find the complexity here — Mitch, May 28 '19 at 20:40
@NathanOliver This isn't really a duplicate of that question, this is a more optimized version of the Sieve algorithm. That's why I am trying to find it's complexity. I do know the original sieve has complexity `n log log n` — Sarah Hyland, May 28 '19 at 20:46
@UlrichEckhardt I think the second for loop is O(sqrt(n)/2) because it iterates to the square root of the vector size (so O(sqrt(n)) and then increments by 2, essentially halving it. — Sarah Hyland, May 28 '19 at 21:37
Not quite. The important point is that the factor of one half is a constant. Check your textbooks how to deal with those. Then, there are several operations there, even in the first three lines of code, and all of them need to be considered, so you need to add those up, for which there are rules. Then, by your reasoning, only the number of rotations in a loop is important, while the body is completely irrelevant. Obviously, that's not true. — Ulrich Eckhardt, May 29 '19 at 06:53

score 0 · Answer 1 · answered May 29 '19 at 08:38

Work performed by basic sieve of Erastophene is almost entirely culling composite numbers and it takes

In your case you start from i * i which effectively reduces number of culling operation by i - 1 for every prime. So, we need to count number of all primes till n (vsize). This is

So, asymptotically we have

Where the last addend is the number of primes less than n.

Time complexity of an algorithm that finds prime numbers given a vector

1 Answers1