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

Question

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)?

Answer 1

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)$.