Information theoretic arguments for complexity

Question

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.

Answer 1

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.