6
$\begingroup$

Wiki says a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

This answer very well explains why primality test algorithm of running time $O(n)$ is actually pseudo-polynomial time. Simply put A very simple way of thinking about it is that if you double the limit, the size of the input only increases by one bit (since the limit is part of the input), while the run time is doubled. That is clearly exponential behavior with respect to the input size.

That is, add one extra bit in the bit representation of your input and the running time will increase exponentially.

Okaaay, My doubt is, isn't it applicable to every algorithm then? Like in sorting. One might say "The main difference is that, in pseudo-polynomial time algorithms, n represents a number in the input, while in other algorithms (sorting) n represents the number of things"

To which I think, how does that matter? Searching maximum in an unsorted array of size $n$ takes $O(n)$ time, add one extra bit to $n$ and the running time will grow exponentially. Hence Shouldn't every algorithm run in pseudo-polynomial time?

Improve this question
$\endgroup$
2
  • $\begingroup$ Why do you think that making one number in an array one bit bigger will make it take exponentially longer to search for a value in that array? It makes one of the numbers exponentially bigger (about twice as big for adding one bit) but you can compare two $k$-bit numbers in $O(k)$ steps, by comparing the bits one by one. $\endgroup$
    – David Richerby
    Jan 20, 2017 at 8:56
  • $\begingroup$ Yes, previously I thought in algorithms (that run in polynomial time) input is just a natural number $n$ and if they iterate over $n^p$ times, their complexity becomes $O(n^p)$. Later I realized the input is not a natural number $n$ but a collection of $n$ things on which the algorithm runs $n^p$ times. Hence polynomial-time running. Ariel cleared my doubts. $\endgroup$
    – Ritwik
    Jan 20, 2017 at 9:06

2 Answers 2

Reset to default
8
$\begingroup$

The running time is always considered with respect to the length of the input.

If the input is a natural number $N\in\mathbb{N}$, then the length of the input is $n=\log N$. In that case, running time of $\Theta(N)$ is actually exponential in the length of the input, $n$.

Suppose now that we're dealing with a problem where the input is a collection of $n$ elements. For simplicity, assume each member in the collection can be represented by a constant number of bits, independent of the input. Lets denote this constant by $c$, so the number of bits required to represent this collection is at most $cn$. In that case, if upon receiving a collection with $n$ elements (which is a $cn$ length input) you preform only $O(n)$ operations, then the running time is linear.

When saying the input is a number $N$, or a list of size $n$, we already talk about the semantics of the input (how we intend to interpret the given sequence of bits). You can count the running time in terms of those "interpretations", e.g. $O(N)$ for naive primality testing, or $O(n)$ for finding a maximum in a list, but in the end you have to remember how those objects relate to the actual input's size. If we denote the length of the input by $l$, for primality testing we have $l=\log N$, so $T(l)=N(l)=2^l$, and for finding maximum $T(l)=n(l)=\frac{1}{c}l$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ okay so what i understand is, running time of type $O(N)$ where N is the input and N∈ℕ, is pseudo-polynomial time however if the input is not a single natural number but instead a collection of objects then the time complexity is number of operations performed on that input. In simple words, algorithms that takes input as a pure natural number and iterate/perform operations as per the number, that algorithm actually runs in pseudo-polynomial time for that input. Am I right? (if yes, can you please tell me more such algorithms, pure polynomial and pseudo-polynomial) $\endgroup$
    – Ritwik
    Jan 18, 2017 at 18:19
  • 1
    $\begingroup$ No. Read the last paragraph carefully, algorithms only deal with sequences of bits, numbers/collections are just examples of interpretations of the inputs (they only exist in our mind). You can count the number of operations any way you like, but eventually, the running time is considered with respect to the input's length (so it's your job to write the number of operations as a function of the input's length, as I wrote on the last line). $\endgroup$
    – Ariel
    Jan 18, 2017 at 18:28
  • $\begingroup$ okay, for an algorithm, an input is nothing but a sequences of bits. Suppose my algorithm runs in polynomial time for a given input BUT the running time increases exponentially with increase in (bits of) input size, then my algorithm runs in pseudo-polynomial time. Isn't it? $\endgroup$
    – Ritwik
    Jan 18, 2017 at 18:50
  • $\begingroup$ Saying the running time is polynomial means that it increases polynomially with the number of bits, not exponentially. You cant have both. $\endgroup$
    – Ariel
    Jan 18, 2017 at 18:54
  • 2
    $\begingroup$ okaay.... now it fits, algorithms like primality testing by iterating from 1 to N (or say sqrt(N)) OR knapsack solution by DP looks like they are running in polynomial time BUT they are running exponentially wrt the input given to them. We think we gave it the number N and it performed N operations hence polynomial (yipiee) but the reality is, we gave it $\log_2{N}$ bits and it performed $2^{\log_2{N}}$ operations. That's why it is running in pseudo-polynomial time. Isn't it? $\endgroup$
    – Ritwik
    Jan 18, 2017 at 19:17
1
$\begingroup$

If you search for the maximum of an array of n elements, the input isn't n. It's n and an array of n elements. The input size is not log n, but a least some multiple of n.

And there are many, many problems where known algorithms are nowhere near pseudo-polynomial. For example: Given n > 0, find the first two consecutive primes p, q such that p - p ≥ n. Or given n > 0, find the n-th Fermat prime.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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