Is $O(n^{1/2})$ exponential? Is $O(n)$ better than $O(n^{1/2})$?

I was just going through some of the primality test algorithms. It seems that the regular one – loop up to square root of $n$ – has running time $O(n^{1/2})$.

Is $O(n^{1/2})$ exponential? And is exponential time better than polynomial always?

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

Here, $n$ 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 $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.

StackExchange Computer Science Q#77668, answer score: 6