Pseudo-polynomial Algorithms - is my understanding right?

Question

In the elegant answer, given by Phrudhvi, to this question What is pseudopolynomial time? How does it differ from polynomial time? it's stated, among many other important points, that under Time Complexity's real, Formal Definition, the TC of their example algorithm is exponential in x.

I understood everything in the answer, except this point here. In the answer, his example alg is O(n^4). He then states that the formal def of TC is based on the number of bits required to represent n. And so, I expected him to say that the TC would be O(x), where x is the number of bits. Instead, he said it's O(2^4x).

I have an idea of why I got confused, and what I think is actually happening. Could you tell me if I'm now right?

Here's why I think I got confused: When Phrudhvi said that formally, TC is based on the number of bits used to represent your input, I thought he meant that the given time required to solve a problem per bit was polynomial, i.e. what people assume TC means about n, but now its linear with each bit, instead.

However, what I now assume he means and what I think is correct is this: even in the formal definition of Time Complexity the time taken for his example and algorithms in general is indeed in fact based on the size of the input n, and is O(n^4) (in his example). However, the size of n grows exponentially with increases in x.

The two expressions of the time complexity are both accurate - but since the formal definition of Time Complexity wants the time taken O(n^4) expressed as a function of x, and n grows exponentially with x, then in terms of x the formal TC is O(2^4x).

Is this right? Many thanks, indeed!

Answer 1

The O(2^4x) formula can be derived from the properties of logarithm as follows:

• O(number_of_bits) = O(log₂n), where n is the input number
• O(2^{number_of_bits}) = O(n), by definition of logarithm
• Rising both sides to 4-th power yields O(2^{4*number_of_bits}) = O(n⁴)

The source of the confusion has to do with labeling the value of the candidate prime with n, and then using O(n⁴) in the rest of the explanation. A better way around this is to start with n being the number of bits required to represent p, a candidate prime. With n bits the value of p is bound by 2ⁿ. If the algorithm is O(p⁴) you get the result O(2^4*n) by simple re-labeling.

Note that OP's estimate that computing n mod i is O(n³) is really conservative. It should be O((log₂n)³) because complexity of mod depends on the number of bits it takes to represent the number, not on the number itself. This does not change the validity of the rest of the answer, though.

Answer 2

If I understand your question rightly, your confusion can be clear quite easily and quickly.

The TC of an algorithm is defined in term of the length of the encoding of the input.
Please, take time to fully understand each term highlighted.

The best way to understand this is to always imagine the input written in the tape of a Turing machine.
If we have an algorithm that takes a number n as its input and computes the n-th triangular number with a loop (i.e. it output 1 + 2 + 3 + ... + n) it's tempting to say that the algorithm is linear since it takes n steps.

This is true in the sense that the algorithm is linear in n but this doesn't tell us the TC of the algorithm because TC is defined in term of the encoding of the number n not n itself.

It's customary to denote the encoding of n with <n>.
For example, possible encodings of 4 are:

       _ _ _
<4> = |1|0|0|
       ¯ ¯ ¯  
       _ _
<4> = |1|1|
       ¯ ¯  
       _
<4> = |4|
       ¯  
       _ _ _ _
<4> = |x|x|x|x|
       ¯ ¯ ¯ ¯  
       _
<4> = |A| 
       ¯

The first three examples are just positional systems (base 2, 3, 10).
The fourth one is an example of a degenerate encoding (it's unary). The last example is a custom encoding where each n has a specific symbol from the encoding alphabet.

While the concept of encoding may seem trivial, it takes time to sip.
You may want to check: numeral.

If we take the binary encoding, a number n has encoding <n> of length about l = log₂(n).
The TC of the algorithm above was n = 2^l.
Thus its TC is exponential.

What if we chose the decimal encoding?
The TC would have been 10^l.
It seems hard, at first, that an algorithm can have no definite TC but in fact TC depends on the computational model, including the encoding.

We usually assume to work in a model where arithmetic operations take only one step.
For example, summing two numbers on a Turing machine takes O(l), while it is customary to make it O(1) on higher models.
Unfortunately, these assumptions are not always stated.

We are not really bothered this much by this though, when working asymptotically with the big-O notation, changing the base of the encoding only change its length by a constant.
In general, if an encoding A can be turned into another encoding B in polynomial time, we don't bother specifying if we are working with A or B because even chaining the encoding translation with the algorithm we still have a polynomial algorithm (if the original one was so).
Related: Polynomial-time reduction.

Now it should be easy to understand the definition of Pseudo-polynomial time given by Wikipedia.

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input.