math - Time complexity of this primality testing algorithm?

Question

I have the following code which determines whether a number is prime:

public static boolean isPrime(int n){
    boolean answer = (n>1)? true: false;

    for(int i = 2; i*i <= n; ++i)
    {
        System.out.printf("%d
", i);
        if(n%i == 0)
        {
            answer = false;
            break;
        }
    }
    return answer;      
}

How can I determine the big-O time complexity of this function? What is the size of the input in this case?

Answer 1

Think about the worst-case runtime of this function, which happens if the number is indeed prime. In that case, the inner loop will execute as many times as possible. Since each iteration of the loop does a constant amount of work, the total work done will therefore be O(number of loop iterations).

So how many loop iterations will there be? Let's look at the loop bounds:

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

Notice that this loop will keep executing as long as i² ≤ n. Therefore, the loop will terminate as soon as i ≥ √n + 1. Consequently, the loop will end up running O(√n) times, so the worst-case time complexity of the function is O(√n).

As to your second question - what is the size of the input? - typically, when looking at primality testing algorithms (or other algorithms that work on large numbers), the size of the input is defined to be the number of bits required to write out the input. In your case, since you're given a number n, the number of bits required to write out n is Θ(log n). This means that "polynomial time" in this case would be something like O(log^k n). Your runtime, O(√n), is not considered polynomial time because O(√n) = O((2^{log n})^1/2), which is exponentially larger than the number of bits required to write out the input.

Hope this helps!