# Is square root of n the same as log n for order notation of an algorithm

Given the context of a basic prime number testing algorithm that has the simple optimization of limiting the potential factors to the range from 2 to the square root of the subject number (instead of 2 to the number - 1) is it true that this efficiency changes the order of the algorithm from O(n) to O(log n)?

We say a function $f(\varepsilon)$ is $\mathcal O (\phi)$ if $\lim_{\varepsilon\to\infty} \frac{f(\varepsilon)}{\phi(\varepsilon)}$ exists. Since,
$$\lim\limits_{n\to\infty} \frac{\sqrt n}{\log n} = \infty$$
the answer is no - i.e. $\mathcal O(\sqrt{n})$ is not the same as $\mathcal O(\log n)$.
• The extra $n$ is a mistake - my apologies! – bashfuloctopus Apr 7 '15 at 14:27
• You're right, it only has to be bounded. Wikipedia's definition says $\lim |f(x)| \leq M |g(x)|$ for some $M > 0$. So it would actually be more correct to say that $\lim\sup \frac{f(\varepsilon)}{\phi(\varepsilon)} < \infty$ since $\lim\sup$ always exists. – bashfuloctopus Apr 7 '15 at 15:05