Is $O(n^{1/2})$ exponential? Is $O(n)$ better than $O(n^{1/2})$?
A function that is $O(n^{1/2}) = O(\sqrt{n})$ is a polynomial, not an exponential, function of&nbsp;$n$. However, when analyzing the run-time of algorithms, we need to be clear about what $n$ actually is.

Here, $n$&nbsp;is the (value of the) number whose primality is being tested. However, we measure the run-time of the algorithm in terms of the length of its input in bits. The number&nbsp;$n$ can be represented in $\log n$ bits, which means that the running time of $O(n^{1/2})$ is actually exponential in the length of the input.