O(n) solution with time complexity analysis - JAVA


  • 1
    C
    public class Solution {
        public int countPrimes(int n) {
            if(n < 3) {
                return 0;
            }
            
            boolean[] status = new boolean[n - 2];  //hold status for number [2 ... n -1]
            
            for(int i = 2; i <= Math.sqrt(n - 1); i++) {
                if(status[i - 2]) { //number i has been traversed, skip it
                    continue;
                }
                for(int j = i; j <= (n - 1) / i; j++) {
                    status[i * j - 2] = true;
                }
            }
    
            int result = 0;
            for(boolean stat : status) {
                if(!stat) {
                    result++;
                }
            }
            
            return result;
        }
    }
    

    Time complexity will be O(N), space complexity is also O(N), which can be reduced by using bit array but still linear.

    Analysis:
    For each number k, which let's say, can be factored as p1 * p2 * ... * pm, it will be traversed m times. Given that k locates within Java Integer range (k <= 2^63 - 1), m will be smaller than 63 since any pi >= 2. Thus, we can find a constant c (c = 63 here), having the running time T <= c * n, which means the time complexity is O(N).


  • 0
    X

    you have an inner for loop and a outer for loop. Time complexity is not O(n)


Log in to reply
 

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