Massachusetts Institute of Technology Professors Ron Rivest and Srini Devadas

Question

There exists a comparison sort of 5 numbers that uses at most 6 comparisons in the worst case.

True or False and Why?

Answer 1

False. The number of leaves of a decision tree which sorts 5 numbers is 5! and the height of the tree is at least lg(5!). Since 5! = 120, 2^6 = 64, and 2^7 = 128, we have 6 < lg(5!) < 7. Thus at least 7 comparisons are required.

Comments

https://ocw.mit.edu/courses/6-046j-introduction-to-algorithms-sma-5503-fall-2005/f0cdfd373e9f8b7c839e7ed13bbfe748_quiz1_sol.pdf