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 :)

  • $\begingroup$ Oh. down vote with no comment :( $\endgroup$ – hqt Aug 31 '12 at 17:32
  • 1
    $\begingroup$ see About some criticisms against down-votes without explanations $\endgroup$ – Tyson Williams Aug 31 '12 at 18:03
  • $\begingroup$ @TysonWilliams I don't want to go to debate for this ;) $\endgroup$ – hqt Aug 31 '12 at 18:30
  • 3
    $\begingroup$ @hqt This question is more appropriate for cs.stackexchange, hopefully the moderators will migrate it there. $\endgroup$ – Yuval Filmus Aug 31 '12 at 18:34
  • 3
    $\begingroup$ Voted to close. This is not a research-level question; the answer can be found in most algorithms textbooks. $\endgroup$ – Jeffε Aug 31 '12 at 20:05

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.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.