<p>Any comparison-based algorithm corresponds to a decision tree. To construct the decision tree, just follow the workings of the algorithm. Each time the algorithm makes a comparison, consider both outcomes. Since the algorithm only has access to the array to be sorted via these comparisons, you don't have to keep any kind of array in mind. Finally, when the algorithm is done, it knows the correct order of the elements in the array. That's exactly the decision tree model.</p>

<p>Each root-to-leaf path in the decision tree corresponds to one possible computation path of the algorithm. The height of the tree is thus the length of the longest computation path, which is a lower bound on the worst-case running time of the algorithm.</p>

CC BY-SA 3.0
2012-08-31T16:23:10.490Z
2012-08-31T16:23:10.490Z
Yuval Filmus
<p>I have read the proof of lower bound of Sorting Algorithm that use comparison to know input is NlogN. In this paper, the author use decision tree for this proof. Everything on this proof I have understand well ( height of decision tree, the inequality is used...) but one thing :</p>

<blockquote>
  <p>lower bound on height equivalent to  lower bound on sorting.</p>
</blockquote>

<p>I have thought so much, but I still cannot understand why. In sorting algorithm, in "normal sense", I feel that there are many ways for sorting (although just use comparison), and I don't see connection between decision tree(to compare n items) to the sorting problem. </p>

<p>Anyone here please give me an idea for this statement.</p>

<p>Thanks :)</p>

CC BY-SA 3.0
2012-08-31T18:34:57.900Z
@hqt This question is more appropriate for cs.stackexchange, hopefully the moderators will migrate it there.
Yuval Filmus
CC BY-SA 3.0
2012-08-31T20:05:30.067Z
Voted to close.  This is not a research-level question; the answer can be found in most algorithms textbooks.
Jeffε
<cc.complexity-theory><ds.algorithms><sorting><decision-trees>
Sorting : proof for lower bound of Sorting
hqt
# Sorting : proof for lower bound of Sorting

(Asked by: username_0 on 2012-08-31)

I have read the proof of lower bound of Sorting Algorithm that use comparison to know input is NlogN. In this paper, the author use decision tree for this proof. Everything on this proof I have understand well ( height of decision tree, the inequality is used...) but one thing :

> lower bound on height equivalent to lower bound on sorting.

I have thought so much, but I still cannot understand why. In sorting algorithm, in "normal sense", I feel that there are many ways for sorting (although just use comparison), and I don't see connection between decision tree(to compare n items) to the sorting problem.

Anyone here please give me an idea for this statement.

Thanks :)

**Tags:** cc.complexity-theory, ds.algorithms, sorting, decision-trees
> **Comments:**
> **username_1**: @hqt This question is more appropriate for cs.stackexchange, hopefully the moderators will migrate it there.  
> **username_2**: Voted to close.  This is not a research-level question; the answer can be found in most algorithms textbooks.  

---

## 1 answers

### Answer by username_1 on 2012-08-31. Score: 2

Any comparison-based algorithm corresponds to a decision tree. To construct the decision tree, just follow the workings of the algorithm. Each time the algorithm makes a comparison, consider both outcomes. Since the algorithm only has access to the array to be sorted via these comparisons, you don't have to keep any kind of array in mind. Finally, when the algorithm is done, it knows the correct order of the elements in the array. That's exactly the decision tree model.

Each root-to-leaf path in the decision tree corresponds to one possible computation path of the algorithm. The height of the tree is thus the length of the longest computation path, which is a lower bound on the worst-case running time of the algorithm.


---

