3
$\begingroup$

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.

$\endgroup$
  • $\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
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

So what is the issue here? The algorithm clearly requires (sqrt(n)//2) divisions by the respect to the N. So if I measure complexity by the function: input number -> #of divisions, then I will get theta(sqrt(n)) complexity.

I believe the actual problem why this algorithm is inefficient that division is not a basic operation, and that the division's complexity is based on the length of divided numbers. Which I didn't see mentioned in any of the responses.

Also there seems to be a misunderstanding in expression of the complexity in "O" notation - O(sqrt(n)) is a subset of O(n) and therefore the algorithms should be more efficient, because power of 0.5 will be less than power of 1 for all positive integers. The other thing is that all algorithms with this (sqrt) complexity can be implemented only in such a way you showed - why is that inefficient. But I state that O(sqrt(x)) <= O (x).

| cite | improve this answer | |
$\endgroup$

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.