5
$\begingroup$

The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$.

However, why don't we emphasize length of input in other algorithms? To name one example, what would be the input size $n$ and worst case time complexity $T$ of the following input when using insertion sort:

111111111,101,11,10,1,0

Answer A: $n=6$, $T=O(n^2)$
Answer B: n = space(all_digits)+space(delimiters_between_numerics)

If B is correct, what is the time complexity $T$?

$\endgroup$
  • $\begingroup$ one way to visualize this. this is not taught/pointed out much in CS classes but theres a perfect proportional/inverse "tradeoff" between size of elements, number of elements, and total [memory] size of the input. for a fixed total memory size you can vary the # of elements to be less but then each one is larger and the total memory size is the same. $\endgroup$ – vzn Jun 29 '13 at 16:04
7
$\begingroup$

First, note that the input length of a Knapsack instance is $\Theta(n \cdot \log \max \{c,w_1,\dots,w_n\})$. Assuming the instance is "pruned", namely that all weights are at most $c$, this is $\Theta(n\log c)$.

In order to answer such questions, you need to fix

  • the machine model,
  • the cost model,
  • the set of valid inputs and
  • the algorithm.

You don't give the first three.

So your question is not well defined. In order store this particular set of numbers on a Turing machine tape, six symbols are indeed sufficient (one per number), and then the algorithm would run in time $O(1)$ on its only input. In order to get a general algorithm, however, you need to "properly" encode the numbers, namely B is the correct answer. I'll assume the latter.

Insertion sort has worst-case complexity $\Theta(n^2)$ in the RAM model with uniform cost model (elementary operations on naturals cost $1$), $n$ being the number of elements. In particular, it is independent of the size of the numbers. Since $n \leq |i|$, $i$ the input, you get an $O(|i|^2)$ time algorithm.

If you apply the logarithmic cost model (elementar operations on naturals have cost depending on their encoding length, cf. elementary school), you get time $\Theta(n^2 \cdot \log E)$ with $E = \log \max\{e_1, \dots, e_n\}$ the length of the largest input number, because the $\Theta(n^2)$ comparisons on the elements dominate the runtime. With similar reasoning as above, we note that the algorithm has runtime $O(|i|^2)$.

So as you can see, the qualitative result does not change when considering the input length for this kind of algorithms, so it is often glossed over. When analysing e.g. radix sort this is no longer valid, and you have to look more closely.

$\endgroup$
  • $\begingroup$ What does it mean by "$n \leq |i|$, $i$ the input"? Don't really get your $i$... $\endgroup$ – wlnirvana Jun 23 '13 at 1:25
  • $\begingroup$ @wlnirvana: The input $i$ is some encoding of $n$ numbers. As the encoding length of each number is at least one, $n \leq |i|$ (the length of the input). $\endgroup$ – Raphael Jun 23 '13 at 10:53
  • $\begingroup$ So once we take the encoding into consideration, it's not that accurate to say insertion sort is $O(n^2)$ because $n$ is not the input size. We'd better say it's $O(|i|^2)$. Am I correct on the point? $\endgroup$ – wlnirvana Jun 25 '13 at 1:37
  • $\begingroup$ @wlnirvana: Technically, that is correct. I argue in my answer why it does not make much of a difference (here). $\endgroup$ – Raphael Jun 25 '13 at 7:04
  • $\begingroup$ Got it. Thanks so much for your clarification. $\endgroup$ – wlnirvana Jun 27 '13 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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