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)?
Asked
Active
Viewed 3,736 times
0
Bohemian
- 183
1 Answers
2
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)$.
bashfuloctopus
- 673
-
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) – Bohemian Apr 06 '15 at 20:56
-
The extra $n$ is a mistake - my apologies! – bashfuloctopus Apr 07 '15 at 14:27
-
This is a little irrelevant, but does the limit of the ratio of the functions have to exist, or can it just be bounded? – Kitegi Apr 07 '15 at 14:36
-
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 07 '15 at 15:05
-
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. – bashfuloctopus Apr 07 '15 at 15:11