0
$\begingroup$

This Wikipedia article,Decision tree model, states that decision tree complexity lower bound $O(n \log_2 n)$ for sorting problem is information theoretic since any algorithm ( modeled as decision tree) must learn $\log_2 n!$ bits of information.

Now, in a Turing machine model (or RAM model), suppose for some computational search problem it is proven that any algorithm must learn $n$ bits of information to produce the solution. The solution is uniquely determined by the $n$ bits. What can we conclude about the complexity lower bound of the problem?

P.S. My motivation is to cary over similar information theoretic lower bound arguments to other computation models. In decision trees model, to solve sorting problem, we have to uniquely identify the permutation that sorts the input list which requires $\log n!$ bits.

$\endgroup$
3
  • $\begingroup$ I don't think your sorting example is precise, since a list of $m$ items generally will need $m \log(m)$ bits of input to represent it, so the amount of information is still equal to the number of bits in the input. $\endgroup$
    – usul
    Aug 11 at 11:29
  • $\begingroup$ @usul The standard notion of input size for sorting problem is the number of elements to be sorted. $\endgroup$ Aug 11 at 14:37
  • $\begingroup$ Yes, and the standard notion for information theory is bits of information... $\endgroup$
    – usul
    Aug 11 at 23:59

1 Answer 1

1
$\begingroup$

If that's the only information you have available, a $\Omega(n)$ lower bound will presumably follow, and presumably this will be the best bound one can hope for in general, as there are plenty of problems whose complexity is $\Theta(n)$ and that can be viewed in some sense as requiring learning $n$ bits of information (e.g., given a $n$-bit bitvector as input, output it).

There is a lot of ambiguity and vagueness in the question you have provided. To make this formal you'd have to give a formal definition of exactly what you mean by "must learn $n$ bits of information", which is currently rather vague.

You can't really carry over the results from the decision tree model to the RAM model. There are known to be problems that can be solved faster in the RAM model than in the decision tree model. As one example, integer sorting can be done faster than $O(n \log n)$ time in the RAM model.

$\endgroup$
0

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.