Why naive primality test algorithm is not polynomial

Question

I would like to understand why the following naive primality test algorithm is not polynomial.

IsPrime (n: an integer)
Begin
   For i=2 to n-1 do
     If (n % i == 0) then
        return (no)
     EndIf
   EndFor

   return (yes)
End

This algorithm is said to be exponential in the size of the input n. Why is it true? And why the following sorting test algorithm is said polynomial and not exponential?

IsSorted (T[n]: an array of n integer)
Begin
  For i = 1 to n-1 do
     If (T[i] > T[i+1]) then
        return (no)
     EndIf
  EndFor

  return (yes)
End

score 5 · Accepted Answer · answered Oct 29 '18 at 09:57

5

The input size is typically measured in bits. To represent the number n the input size would be log2(n). The primitive primality test is linear in n, but exponential in log2(n).

answered Oct 29 '18 at 09:57

Henry

42,982
7
68
84

So using the big-O notation, the complexity would be O(2^(log2(n)) which exponential ? – M . Franklin Oct 29 '18 at 11:34
Yes, written a little differently O(2^k) where k is the input size in bits. – Henry Oct 29 '18 at 11:58
Thanks I now understand it better – M . Franklin Oct 29 '18 at 14:37
How many bits do I need to encode and an array of n integers? – M . Franklin Oct 29 '18 at 14:39
n times the size of an integer (=32) so 32n. – Henry Oct 29 '18 at 14:40
If each number is in k bits, then the complexity of IsSorted should be O(nk) = O(n) since k is a constant that doesn't depend on the size of the input array. Am I right ? – M . Franklin Oct 29 '18 at 14:48
To my understanding above statement is correct. – venkysmarty Oct 16 '21 at 02:06

Codor · Answer 2 · 2021-10-17T10:26:55.953

To second the answer given by Henry, the algorithm in the original question in fact has a polynomially bounded running time - if unary encoding is used for the input!

More precisely, the runtime bound does not only depend on the algorithm itself but also the used encoding scheme. Consider the following algorithm in C-like syntax.

INPUT: integer n
for (int i = 0; i < n; i++)
{
    wait one second
}

Apparently, the algorithm takes n seconds to terminate; the time is linear in n. If the input is encoded using unary encoding, the amount of time scales linearly in the encoding length of n. However, if n is encoded using binary encoding the amount of time scales exponentially in the encoding length of n (as the encoding length of n scales logarithmically in the value of n).

To put it all in a nutshell, the statement that the algorithm in the question is not polynomial without any additional information is not correct. However, apparently it is a convention that binary encoding (or any other positional notation) is used unless otherwise stated.

That being said, I admit that the depenence of the runtime bound on the encoding scheme tends to be taught a bit imprecisely. The term pseudopolynomial is also floating around.

score 2 · Answer 3 · answered Oct 29 '18 at 12:55

The naive primarily test is polynomial in the value of the input (that is, the actual number which the function receives), but exponential in the size (bits, bytes, etc.) of the input.

If you have a number n consisting of b bits, we have b = O(log n) and also n = O(2^b).

The running time is thus O(n) or O(2^b).

Why naive primality test algorithm is not polynomial

3 Answers3

Linked