5
$\begingroup$

Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$.

I iterate from $i=2$ to $\sqrt{n}$ and continuously checking if n%i != 0.

However, do we consider the complexity of the square root function also?

If we do, the Newtons method for finding square roots has a complexity of $n^2$.

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ It depends what model of computation you're using and how you measure the length of the input. In some computation models, we assume we can add numbers of arbitrary size in constant time; in others, we assume that you have to add up the digits one by one (the same way you'd calculate 283746+384273). The other issue is that we normally write $n$ for the number of bits in the input. A $b$-bit number could have any value up to $2^b$ so the algorithm you describe is actually exponential in the number of bits (you check $\sqrt{2^b} = 2^{b/2}$ potential divisors). $\endgroup$ – David Richerby Oct 7 '15 at 8:15
  • 8
    $\begingroup$ Your question is not about "the complexity of checking primality" but about the complexity of a specific algorithm for this task. Prime checking in general can be done in polynomial time with AKS. $\endgroup$ – Tom van der Zanden Oct 7 '15 at 8:19
  • $\begingroup$ math.dartmouth.edu/~carlp/aks06-2015.pdf ​ ​ $\endgroup$ – user12859 Oct 7 '15 at 9:53
  • 6
    $\begingroup$ You can avoid computing $\sqrt{n}$ (which doesn't have complexity $\Theta(n^2)$, but rather polylogarithmic in $n$) by checking whether $i^2 \leq n$. You can even avoid computing $i^2$ by updating it using the rule $(i+1)^2 = i^2 + 2i + 1$. $\endgroup$ – Yuval Filmus Oct 7 '15 at 20:40
  • $\begingroup$ @DavidRicherby does this mean counting has 2^b runtime ? $\endgroup$ – HopefullyHelpful Aug 30 '16 at 20:57
10
$\begingroup$

When $n$ is the input, we test $\sqrt{n}$ divisors. However, we also have to take into account the complexity of division itself. For a number with $b$ bits, this takes $O(b \log b \log\log b)$ operations, when we are using the Schönhage–Strassen algorithm. Since half of the numbers below $\sqrt{n}$ have $\log(\sqrt{n})$ digits, we may assume the all have this amount of digits. It only matters a factor $\frac12$ at most, and that is absorbed in the $O$.

This gives a computational complexity of $O( \sqrt{n} \log \sqrt{n}\log(\log(\sqrt{n}) ) \log\log(\log(\sqrt{n}) )))$. We can simplify this to $O( \sqrt{n} \log(n) \log(\log(n) ) \log(\log(\log(n) )))$.

However, when notating it using the number of bits $b$ of a number, which is more standard usage, we get a computational complexity of $O(2^{b/2} b \log b \log\log b)$.

You also need to compute $\sqrt{n}$ but that has only complexity $O(b \log b \log\log b)$ when using Newton's method and the Schönhage-Strassen algorithm.

However, this is not optimal. The current best algorithm, the AKS algorithm, reaches a complexity of less than $O(b^{7})$ worst-case , which is much faster. (To be precise, even $O(b^{6+\varepsilon})$ for any $\varepsilon>0$ has been shown, but that is more complicated than it needs to be for this answer.)

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The square root only needs to be calculated once, so the time is tiny compared to everything else. $\endgroup$ – gnasher729 Jul 6 '16 at 22:57
  • 1
    $\begingroup$ Isn't it confusion to use bit notation for anything ? I mean counting from 1 to n is 2^b in bit notation. I have seen plenty of people thinking that integer factorization has exponential runtime, when counting has a worse exponential runtime using the same notation. $\endgroup$ – HopefullyHelpful Aug 30 '16 at 20:52
2
$\begingroup$

A recent famous result is that checking if a number of $n$ bits is prime can be done in time polynomial in $n$, see the AKS test (it's somewhat heavy going).

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ This is mentioned in the other answer as well as in the comments to the question itself. $\endgroup$ – Yuval Filmus Feb 14 '16 at 23:48

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.