<p>If that's the only information you have available, a <span class="math-container">$\Omega(n)$</span> 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 <span class="math-container">$\Theta(n)$</span> and that can be viewed in some sense as requiring learning <span class="math-container">$n$</span> bits of information (e.g., given a <span class="math-container">$n$</span>-bit bitvector as input, output it).</p>
<p>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 &quot;must learn <span class="math-container">$n$</span> bits of information&quot;, which is currently rather vague.</p>
<p>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 <span class="math-container">$O(n \log n)$</span> time in the RAM model.</p>

CC BY-SA 4.0
2022-08-08T02:24:19.797Z
2022-08-08T06:22:31.877Z
2022-08-08T06:22:31.877Z
D.W.
<p>This Wikipedia article,<a href="https://en.m.wikipedia.org/wiki/Decision_tree_model#Comparison_trees_and_lower_bounds_for_sorting" rel="nofollow noreferrer">Decision tree model</a>, states that decision tree complexity lower bound <span class="math-container">$O(n \log_2 n)$</span> for sorting problem is information theoretic since any algorithm (  modeled as decision tree) must learn <span class="math-container">$\log_2 n!$</span> bits of information.</p>
<p>Now, in a Turing machine model (or RAM model), suppose for some computational search problem it is proven that any algorithm must learn <span class="math-container">$n$</span> bits of information to produce the solution. The solution is uniquely determined  by the <span class="math-container">$n$</span> bits. What can we conclude about the complexity lower bound of the problem?</p>
<p>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 <span class="math-container">$\log n!$</span> bits.</p>

CC BY-SA 4.0
2022-08-11T11:29:32.270Z
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.
usul
CC BY-SA 4.0
2022-08-11T14:37:43.897Z
@usul The standard notion of input size for sorting problem is the number of elements to be sorted.
Mohammad Al-Turkistany
CC BY-SA 4.0
2022-08-11T23:59:17.650Z
Yes, and the standard notion for information theory is bits of information...
usul
<cc.complexity-theory><it.information-theory>
Information theoretic arguments for complexity
Mohammad Al-Turkistany
# Information theoretic arguments for complexity

(Asked by: username_0 on 2022-08-07)

This Wikipedia article,[Decision tree model](https://en.m.wikipedia.org/wiki/Decision_tree_model#Comparison_trees_and_lower_bounds_for_sorting), 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.

**Tags:** cc.complexity-theory, it.information-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: @usul The standard notion of input size for sorting problem is the number of elements to be sorted.  
> **username_1**: Yes, and the standard notion for information theory is bits of information...  

---

## 1 answers

### Answer by username_2 on 2022-08-08. Score: 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.


---

