[Solved]: Why don't we emphasize "length of input string" when considering time complexity of sorting algorithms?

Problem Detail: 

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$?

Asked By : wlnirvana

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12825

3.2K people like this

 Download Related Notes/Documents