Counting Prime with time complexity of O(n log log n) - Sieve of Erathosthenes solution


  • 1
    S
    public class Solution {
    public int countPrimes(int n) {
        if(n < 3)
            return 0;
        int[] pArray = new int[n+1];
        int primeCount =0;
        for(int i =2; i < pArray.length-1; i++)
        {
            if(pArray[i]==-1)
                continue;
            primeCount++;
            int num = i;
            while(num < pArray.length-1)
            {
                pArray[num] = -1;
                num += i;
            }
        }
        return primeCount;
    }
    }
    

    It goes twice over the array O(2n) which can be taken same as O(n). Once to check all number if they are prime or not, second if a number is prime (not marked as -1) then make all its multiple as -1.


  • 0

    Your lists are nested, not one after the other, so with a simple analysis like that, you get O(n2), not O(2n).


  • 0
    S

    Okay, It is nested but not every nested loops are order of N^2. I agree that it will certainly take more than O(2n). But only for number which are multiple of LCM of two prime numbers. And as the prime number increases in its value, the LCM becomes higher and hence for average cases it wont repeat much. O(n^2) is too loose an upper bound a tigher upper bound will be n(1/2 + 1/3 + 1/5 + 1/7 + …) because Say for n=100. The 2, will cover 1/2 of number, then n=3, will cover 1/3 of number, n=5 will cover 1/5 of number and so on... So it is certainly better than (n^2) but worst than O(n).
    It is O(n*(1/2 + 1/3 + 1/5 + 1/7 + …))


  • 0
    W
    This post is deleted!

  • 0
    P

    please edit you answer, its O(n^2). I was gazing at the solution when you said O(n) until I read the comments section... Thanks for help anyways.


  • 0
    S

    Hey, I have updated the title with a reasonable upper bound.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.