3
$\begingroup$

From wikipedia

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required to represent it) and the numeric value of the input (the largest integer present in the input). In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.

From this SO post

An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

I have some questions about the wiki definition. To my knowledge, the definition provided by the SO post makes more sense. Shouldn't the wiki say pseudo-polynomial time is if the running time is
1) exponential (or something greater than polynomial) in the length of the input, and
2) polynomial in the numeric value of the input (largest number of input)
??

Assuming you have answered the question of definition above,

I am having trouble analyzing the running time of Counting Sort which is $O(N + K)$ with respect to $N, K$, the numeric values of the input.

Assuming we do not have the $k = \Theta(N)$ simplifying condition, the length of the input is $x = \Theta(N\log(k))$ bits.

The Wiki says "In general, the numeric value of the input is exponential in the input length". But $k = 2^{\Theta(\frac{x}{N})}$. With N potentially bringing down the magnitude of the exponent, I don't really see how $k$ is exponential in $x$.

In addition, the SO post I referenced claims counting sort runtime is exponential with respect to the length of the input, $x = \Theta(N\log(k))$ bits. How can $O(N + k)$ be transformed into an expression exponential in $n$ to demonstrate the claim? I got it down to $O(\frac{x}{\log(x)} + k)$ but got stuck there.

If I just think the length of the input is $\Theta(\log k)$ then I can see why the run-time is exponential but this doesn't seem to be consistent with how $x$ should be defined.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let us denote the input's length by $n$, and lets remember that $n=\Theta\left(N\log K\right)$. You won't be able to write the exact running time of counting sort as an expression of the form $2^{\Omega(n)}$, as this would mean that for large enough inputs, the running time is always exponential. However, in this case, if $K$ is not too large compared to $N$, then the running time is actually linear, this means that there exists an infinite series of inputs with increasing size on which the running time is not exponential.

With this is mind, recall that what you seek is the worst case complexity of your algorithm, i.e. you want to find a certain time bound that holds for all inputs of large enough size. This means that to lower bound the complexity, it suffices to find one series of inputs with increasing size on which the running time is exponential. This allows you to focus on inputs where $K=2^N$, in this case the input size is $n=\Theta\left(\log^2 K\right)$, and the running time is $O(K)=O\left(2^{\sqrt{n}}\right)$, which is definitely exponential.

In general, a pseudopolynomial time algorithm is an algorithm which runs in polynomial time in the numeric value of the input (which means it is not necessarily polynomial in the input's length). Wiki's definition is no different, except it adds the restriction that the running time is polynomial in both the numeric value and the input size, i.e. if the input size is $n$, and its associated numeric value is $v$, we want a time bound of the form $p(n,v)$ for some polynomial $p$. This excludes for example a $2^N+K$ time algorithm for sorting $N$ numbers in the range $[1,K]$, although this is polynomial in $K$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ So when $k \geq 2^{N}$, our worst case, the lower bound running time is exponential with respect to length of the input. But when $k$ is of lower order of magnitude with respect to N, I will assume $k = N^{O(1)}$, then $n = \Theta(N\log N)$ and $O(N+K) = O(N^{O(1)})$. Since $N = \Theta(\frac{n}{\log N}) = \Theta(\frac{n}{\log n})$, we have $O((\frac{n}{\log n})^{O(1)})$. And when $N^1$, we have runtime sub-linear with respect to $n$? Is this analysis correct and considers different cases almost exhaustively? $\endgroup$
    – namesake22
    Commented Jan 9, 2018 at 7:37
  • $\begingroup$ Your analysis seems correct. If you don't care about logarithmic terms you could simplify and conclude that if $K=N^{O(1)}$ the algorithm runs in polynomial time. You will not get sublinear running time for $K=O(n)$, note that sublinear running time does not even allow you to read the entire input. $\endgroup$
    – Ariel
    Commented Jan 9, 2018 at 11:44
  • $\begingroup$ I see no difference between wiki and the post you quoted. A pseudopolynomial time algorithm is an algorithm which runs in polynomial time in the numeric value of the input (which means it is not necessarily polynomial in the input's length). Perhaps what is confusing you is that the wiki definition talks about a polynomial in two variables, i.e. if $n$ is the input's length and $v$ is the numeric value of the input, Wiki states that the running time should be $poly(n,v)$, which is not necessarily bounded by $poly(n)$ since $v$ can be exponential in $n$. $\endgroup$
    – Ariel
    Commented Jan 9, 2018 at 11:59
  • 1
    $\begingroup$ See multivariate polynomial. If the input of the problem is a natural number $N$ encoded in binary, then the input size is $n=\log N$, and the numeric value is $v=N=2^n$, which makes it exponential. For your sorting example, the answer shows that the numeric value $K$ can be exponential in the input size $n$, if $K=2^N$. $\endgroup$
    – Ariel
    Commented Jan 9, 2018 at 22:30
  • 1
    $\begingroup$ The $O(N+K)$ complexity of counting sort is achieved in the word-ram model of computation, see this answer for details. In the usual multitape Turing machine model, you will get an extra $\log K$ factor, which resolves your sublinear running time problem. Feel free to simplify the comments (though they are no longer editable, you can only remove them and post new ones). $\endgroup$
    – Ariel
    Commented Jan 11, 2018 at 20:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.