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

  • $\begingroup$ Why have you compared O(n log n)? I asked about O(log n). Still, it seems it doesn't change your finding that sqrt n is not the same order as log n. Can the big O of sqrt(n) be expressed as a function of log (n)!? Many big O expressions include lig(n) $\endgroup$ – Bohemian Apr 6 '15 at 20:56
  • $\begingroup$ The extra $n$ is a mistake - my apologies! $\endgroup$ – bashfuloctopus Apr 7 '15 at 14:27
  • $\begingroup$ This is a little irrelevant, but does the limit of the ratio of the functions have to exist, or can it just be bounded? $\endgroup$ – Kitegi Apr 7 '15 at 14:36
  • $\begingroup$ 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. $\endgroup$ – bashfuloctopus Apr 7 '15 at 15:05
  • $\begingroup$ That being said, I cannot think of an example of an algorithm (off the top of my head) for which the limit would not exist. Likely, it could be something that depends on parity. $\endgroup$ – bashfuloctopus Apr 7 '15 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.