In the paper "PRIMES is in P" the following is said (page 1):

Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.

Firstly, isn't complexity $\sqrt{n}$ already polynomial?

Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.

  • $\begingroup$ Try to understand the concept of pseudo-polynomial time. It will answer your question. $\endgroup$ – Mario Cervera Feb 21 '18 at 12:20
  • $\begingroup$ In twenty seconds I can write down a number that this method won’t factor in a lifetime. $\endgroup$ – gnasher729 Feb 22 '18 at 18:58

The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.

The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.

As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.


newbie's answer already explains it all. But if I had to add something to this, I'd put it in simpler words.

When you talk about a polynomial time algorithm, what you actually mean is that the running time of the algorithm is a polynomial in the input length. The input length is, roughly speaking, the number of keystrokes required to express the input.

To see why $O(\sqrt{n})$ is not polynomial in the input length, consider what happens when you add a new digit to the right end of your input. This requires just one extra keystroke. So, the input length goes up by just one. However, note that the value of the input goes up by a factor of $10$. So, now you need to do $\sqrt{10}\approx 3$ times as many divisions to check if your input is prime or not. Increasing the input length by just one results in a $3$-fold increase in work. This is clearly exponential.

The $O(\sqrt{n})$ time algorithm is an example of a pseudo-polynomial time algorithm. These are algorithms whose running times are a polynomial in the numeric value of the input, but not necessarily in the length of the input. Another common example of a pseudo-polynomial time algorithm is the dynamic programming algorithm for $0-1$ knapsack.


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.