1
$\begingroup$

All the proofs I've seen about the Ω(nlgn) lower-bound for comparison sorts use binary decision tress like this (from CLRS textbook) enter image description here

Now what if each comparison yields strictly 3 outcomes, i.e. <, =, >? (the input array is allowed to contain repeated elements)

The bound is probably still Ω(nlgn), but I'm not sure how one would draw the (not necessarily full) ternary decision tree (still with unique leaf nodes); this kind of tree is mentioned in the proof of the water jug problem.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The proof would be exactly the same, using a ternary tree (where each internal node has three children) instead of a binary tree. A ternary tree of depth $d$ has at most $O(3^d)$ notes, so a sorting tree would have to satisfy $n! = O(3^d)$, which implies that $d = \Omega(n\log n)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I mostly agree with you; however I'm interested in some graphical representation of such a ternary tree. Say n=3, it's not clear to me what the children of the node a1==a2 should be. Depending on the representation, internal nodes could have less than 3 children $\endgroup$
    – Yibo Yang
    Oct 2, 2016 at 22:36
  • $\begingroup$ @YiboYang It looks exactly the same. You're right that some nodes could be unreachable, but the same holds in the usual case. $\endgroup$
    – Yuval Filmus
    Oct 2, 2016 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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