Why naive primality test algorithm is not polynomial

user_7290876 0
Viewed 853

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
time-complexity algorithm
3 Answers

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

user_17965790

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.

user_33554760

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(2b).

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

user_17117960
Related