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.

$\endgroup$
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)$.

$\endgroup$
  • $\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 '16 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 '16 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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