8
$\begingroup$

The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time correctly.

My current understanding is that pseudo polynomial time means polynomial in the magnitude of the input, and polynomial time is polynomial in the number of bits it takes to represent the input. Thus, looking through each element of an array is $O(n)$ in the magnitude of its length (pseudo-polynomial), but it is exponential in the number of bits in the length of the array. In the same way, binary search is $O(log_2 n)$ in the magnitude of the length of $n$, but is linear in the number of bits in $n$ making it "pseudo-logarithmic".

If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?

Improve this question
$\endgroup$
4
  • $\begingroup$ Binary search is $O(\log n)$ because we want to compare it to linear search where you need to examine every element. Also, each element could be a complex object and its size does not affect the run time while the input in knapsack problem are integers that affect the run time. Therefore, it is natural to express the complexity of binary search in terms of the number of elements $n$. So, $n$ in binary search represents the number of elements while $W$ represents integer's magnitude which needs $\log W$ to store. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Jul 5, 2013 at 21:40
  • $\begingroup$ It's spelled 'pseudo', not 'psudo'. Please edit $\endgroup$
    – Alessandro Cosentino
    Commented Jul 5, 2013 at 23:25
  • $\begingroup$ See cs.stackexchange.com/q/12981/41 $\endgroup$
    – Kaveh
    Commented Jul 6, 2013 at 6:35
  • 1
    $\begingroup$ A very good explanation of pseudo polynomial is given here: stackoverflow.com/questions/19647658/… $\endgroup$
    – bogdan.rusu
    Commented Nov 22, 2015 at 20:29

2 Answers 2

Reset to default
4
$\begingroup$

The running time for binary search that you quote applies for the so-called RAM model. I think that it is usually assumed that the machine words have size $\Theta(\log n)$ bits, where $n$ is some natural parameter like the length of the input.

For binary search, the input has size $\Theta(n)$, assuming that the array's datatype fits in a constant number of machine words, and so the running time $O(\log n)$ is logarithmic in the input size. The running time of the dynamic programming algorithm for knapsack is $\Theta(nW)$, but the size of the input is $O(n\log W)$ (in fact somewhat less, since machine words have superconstant size). This is not polynomial in the size of the input. However, if the weights are encoded in unary, then the size of the input is $O(nW)$ (again, actually somewhat less), and so the algorithm is pseudo-polynomial. It's a matter of encoding - whether you encode the weights in binary or in unary.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Why "machine words have size Θ(logn) bits" instead of "machine words have size log2n bits" (the real expression) ? I know that the logarithm base does not matter in the complexity order, but it seems to me that using the order instead of the real expression makes the statement a little less clear. $\endgroup$
    – Alan Evangelista
    Commented Nov 11, 2019 at 9:19
  • $\begingroup$ Machine words have size $w$ which satisfies $w = \Theta(\log n)$. Perhaps some people insist on exactly $\log_2 n$, but it makes no difference. Indeed, sometimes it makes sense to have larger word size, for example if we think of an array as a sequence of words, and we allow each array entry to have polynomial size (rather than exactly $n$). $\endgroup$
    – Yuval Filmus
    Commented Nov 11, 2019 at 9:45
  • $\begingroup$ You mean that it makes no difference in algorithm complexity analysis because N is very large and because that theory is more concerned with upper/lower bounds, right? I am pretty sure that the logarithm base makes a big difference in a generic calculation. Sorry if that is obvious in the Computational Complexity Theory. $\endgroup$
    – Alan Evangelista
    Commented Nov 11, 2019 at 9:49
  • 1
    $\begingroup$ It makes no difference in the asymptotic analysis of running times (it only changes the running time by a constant factor). We never bother to compute absolute complexity, since it makes little sense, since we don't even have a standard model that everyone agrees about. $\endgroup$
    – Yuval Filmus
    Commented Nov 11, 2019 at 9:51
  • $\begingroup$ Thanks for making it clear. Another question: why is the machine word (64 bits in most computer nowadays) even relevant to this question if the definition of size input used for all algorithms is "the number of bits in the input" (independent of the size of the word)? $\endgroup$
    – Alan Evangelista
    Commented Nov 11, 2019 at 10:16
1
$\begingroup$

If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?

It depends on the perspective from which one tackle the problem. Often, when dealing with numbers, people tend to give more importance to the number of bits. Why is that ? Simply because numbers problem comes from their size (number of digits or bits).

e.g.

  • 0/1 knapsach problem: It runs in O(nW) time (see wikipedia). "n" being the number of items and "W" is the maximum weight. A large weight means a very large number, which is critical. A large number of items depends on the size of items, which reduces to W. The size of number grows exponentially when expressed in terms of bits (2x). For this reason people care more about size input data in terms of bits.
  • is prime problem: An algorithm for finding out whether a number N is prime or not. It is quite easy to compute it for a 10 digit number, but harder as we go for large numbers. The number of bits here are important and grows exponentially.
  • binary search: it runs in log2(n), but has a linear growth in terms of number of bits. It needs a really very big data set, which means a very big bit encoding so to make it impossible to run the algorithm in a reasonable amount of time.

In the first examples, there is a significant difference between the real data size and data representation: We can easily give as input 300 digit number (relatively small), but it's encoding in binary code is TOO BIG, which influences the binary operations.

However in the case of "binary search", the different between data representation and real data size is constant.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @DavidRicherby I edited the answer, is it clear ? $\endgroup$
    – haitam
    Commented Feb 14, 2015 at 18:10
  • $\begingroup$ Yes, I think that's a big improvement. $\endgroup$
    – David Richerby
    Commented Feb 14, 2015 at 18:40

Your Answer

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