In this tutorial, we’ll talk about the difference between pseudo-polynomial and polynomial complexities.
The goal of time-complexity analysis is to derive asymptotic bound(s) of the number of steps an algorithm executes as its input grows in size. For instance, the time complexity means that if the input’s size grows indefinitely, the algorithm will perform at most steps, where is a positive constant. Translating steps to time units, we’ll get that the duration is also a quadratic function of .
That, however, brings up a question of the input size. What is an appropriate measure of the size of an input?
2.1. The Size Is the Number of Bits
In the algorithm analysis, the input size is the number of bits needed to write it down. For example, if the input is an array with integers, the actual size for analysis is or , depending on how we store integer numbers at the machine level. Likewise, the size of an matrix is or .
2.2. We Can Count the Elements and Get Correct Results
In general, the following rule applies:
If all the elements are of the same type, which is mostly the case, we have:
As long as the number of bits per single element is a constant for the total number of input elements, we can ignore it in the analysis. Why? Because multiplicative constants don’t change the complexity.
Therefore, it’s safe to use as the size of an -element array, which we do in practice. The same goes for other input types such as, e.g., matrices.
3. The Pseudo-Polynomial Complexity
What if we express complexity in terms of the input’s magnitude instead of the number of bits?
Let’s say that instead of , we use , where constitute the input to our algorithm. The technical details of the analysis won’t change. The same tools like the Master and Akra-Bazzi Theorems will apply. However, we may get a different result than if we used the standard definition of the input size. For that reason, we say that an algorithm whose complexity is is pseudo-polynomial. Let’s take a look at an example.
3.1. A Pseudo-Polynomial Primality Problem
Here’s the pseudocode of a simple way to check if a number is prime:
The algorithm executes at most iterations. To simplify things, we’ll assume that our machine has an low-level method of computing . Then, we can conclude that the algorithm’s time complexity is .
However, we need bits to store the input number in memory. Since , the complexity in terms of the size is . So, is the algorithm linear or exponential?
Since the computers store data as binary strings (consisting of zeroes and ones), the latter result is more in line with how they carry out the computation. On the other hand, if we had computers that could store any number in a single memory cell, expressing the complexity in terms of the numeric values would be more appropriate. So, it all comes down to what is a more natural and more reasonable representation of the input.
4. Why Do We Care About Pseudo-Polynomial Complexity?
Since grows slowly with , the exponential nature of numerical algorithms will materialize only if the input number is sufficiently large. So, if we could bound its value or be certain that it will be reasonably low most of the time, we shouldn’t worry too much about time complexity.
But the converse also holds. If we want to make a numerical algorithm slow, the pseudo-polynomial complexity tells us to use exceptionally large numbers. That’s the case in, e.g., cryptography. For example, we couldn’t rely on RSA as the encryption algorithm if we could factor numbers efficiently in a polynomial time. So, the users of RSA encryption choose such prime factors and that factoring their product is beyond the current computational capabilities of any attacker.
In this article, we talked about pseudo-polynomial algorithms. They are polynomial in the input’s magnitude. However, as we illustrated with an example, such algorithms aren’t polynomial in the number of bits we need to store their inputs.