Count Primes - Time Complexity

Question

What is the time complexity of this algorithm, in terms of n?

public int countPrimes(int n) {
   boolean[] isPrime = new boolean[n];
   for (int i = 2; i < n; i++) {
      isPrime[i] = true;
   }

   // Loop's ending condition is i * i < n instead of i < sqrt(n)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i < n; i++) {
      if (!isPrime[i]) continue;
      for (int j = i * i; j < n; j += i) {
         isPrime[j] = false;
      }
   }
   int count = 0;
   for (int i = 2; i < n; i++) {
      if (isPrime[i]) count++;
   }
   return count;
}

Credit: https://leetcode.com/problems/count-primes/

Answer 1

public int countPrimes(int n) {
   boolean[] isPrime = new boolean[n];

// executes n times 
   for (int i = 2; i < n; i++) {
      isPrime[i] = true;
   }

   // Loop's ending condition is i * i < n instead of i < sqrt(n)
   // to avoid repeatedly calling an expensive function sqrt().

// The outer loop executes (square roots of n) times 
   for (int i = 2; i * i < n; i++) {

// Test: constant 

      if (!isPrime[i]) // then part constant continue;

// The inner loop executes (square roots of n) times 
      for (int j = i * i; j < n; j += i) {
         isPrime[j] = false;
      }
   }
   int count = 0;

// executes n times 
   for (int i = 2; i < n; i++) {

// Test: constant 
      if (isPrime[i]) count++;
   }
   return count;
}

Total time= n + c₁² * (square root of n)² +  c₂n = O (n) 

Answer 2

I have given a shot at it, please have a look and share your comments:

https://photos.google.com/share/AF1QipOUYvkzTR89ME_ViLUyojoFDBcXkq4MaH9uefI3YD4fB2wIFBE4po1M466wNebZdA?key=THpMR3RiSXBUOEVjZWFTNzlCWnVDczhMVzBxQ09B

https://photos.google.com/share/AF1QipMrp2dJRWSknQFLLb2XgXm1mpWIip_MqVa5Z3imtgGgt75Sv6vSV2wLVA6WAD4ykA?key=VHJReWpxZlRvWk5kVFhfbURybWIybThoTGljclR3

Explanation:

public int countPrimes(int n) {
   boolean[] isPrime = new boolean[n];
   for (int i = 2; i < n; i++) {
      isPrime[i] = true;
   } // It will iterate n-times, hence o(n)

   // Loop's ending condition is i * i < n instead of i < sqrt(n)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i < n; i++) {
      if (!isPrime[i]) continue;
      for (int j = i * i; j < n; j += i) {
         isPrime[j] = false;
      }
   }
   int count = 0;
   for (int i = 2; i < n; i++) {
      if (isPrime[i]) count++;
   } // It will iterate n-times, hence o(n)
   return count;
}

For the second loop:

   for (int i = 2; i * i < n; i++) {

----------------------------

----------------------------

----------------------------
    } // it would run for (sqrt(n)-1) times

From i=2 to i^2<n

For the third loop:

      for (int j = i * i; j < n; j += i) {
         isPrime[j] = false;
      }
For the first iteration of i, the value of j would be:

2, 4, 6, 8………….sqrt(n)/2

For the second iteration of i, the value of j would be:

3, 6, 9, 12………….sqrt(n)/3

For the third iteration of i, the value of j would be:

4, 8, 12, 16………….sqrt(n)/4

When I is just less than sqrt(n)

It would run for only 1 time.

Therefore, no. of iterations for second and third loop:

sqrt(n)(1/2 + 1/3 + 1/4 +  ------ + 1/sqrt(n))

= sqrt(n)(log(sqrt(n)))  = sqrt(n)/2 * (log(n)) 

So, the total complexity of algorithm in term of n would be:

= n + sqrt(n)/2 * (log(n)) + n

Thanks