CODEWITHSUNDEEP
c++time-complexitybig-oprimality-test
Greg
Greg

Reputation: 69

Time Complexity of this primality test function

What would be the time complexity of this function

bool prime(int n) {
    if(n <= 1) {
        return false;
    } else if(n <= 3) {
        return true;
    } else if(n % 2 == 0 || n % 3 == 0) {
        return false;
    } else {
        for(int i = 5; i * i <= n; i += 6) {
            if(n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
    }
    return true;
}

If I had to guess, it would be

O(sqrt(log(n)))

Upvotes: 2

Views: 527

Answers (1)

Marek R
Marek R

Reputation: 38052

Each if is constant time.

for loop is executed until i * i reaches n this means it is executed sqrt(n) / 6 times. So complexity is O(sqrt(n)).

It doesn't meter that density of prime numbers is proportional to 1/log(n) (probably this is source of log(n) in your solution.

Note that time complexity (no adjective) usually is consider as worst time complexity:

Time complexity - Wikipedia

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity

Average time complexity is much harder to compute in this case. You would have to prove how fast loop terminates on average when n is not a prime number.

Upvotes: 1

Related Questions