Why Is This Algorithm Not In Polynomial Time?

Question

so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't understand what my professor meant by that even after he talked about it. When I looked at this problem I thought that is in polynomial time due the for loop iterating n times making it O(n).

The Algorithm description and Pseudocode are shown below:

A proper factor of positive integer n is a positive integer k that is a factor of n and where 1 ≤ k < n. A positive integer n is perfect if and only if the sum of all of the proper factors of n is equal to n. For example, 6 is perfect because the proper factors of 6 are 1, 2 and 3, and 1 + 2 + 3 = 6. The following algorithm determines whether positive integer n is perfect. Is it a polynomial-time algorithm? Explain why or why not.

isPerfect(n)
sum = 0
for i = 1, ..., n
if i is a factor of n
sum = sum + i
end if
end for
if sum == n
return true
else
return false

Answer 1

It’s not a polynomial time algorithm. Think what happens when you add one more bit to the input ($n$); You may end up doing twice the iterations you did before. When we say an algorithm is polynomial, it makes $\text{polynomial}(x)$ calculations where $x$ is the size of the input. In this case, the size of the input is the number of bits used to describe $n$ is $log n$. The algorithm may end up doing $2^x$ iterations - not polynomial.

Answer 2

The distinction to make is that the input can be represented in $k = \log n$ bits. Thus, if an algorithm runs in $O(n)$ time, it really runs in $O(2^k)$ time, if we are considering the size of the input (which we usually are). So even though it runs in linear time in terms of the value of the input, it’s not necessarily polynomial time in terms of the size of the input. While we are sometimes concerned with the former, the latter is more commonly used when discussing complexity (e.g. this algorithm wouldn’t show that the language of perfect numbers is in $P$). It’s also common to refer to this former class (where runtime is polynomial in the value of the input) as “pseudo-polynomial,” rather than the stricter “polynomial.”