Lower Bound Assumptions II

• Assume that all keys are distinct, since all sort algorithms must handle this case.

• Because there are no “tricks” that work, the only information we can get from a key comparison is:

• Which key is larger

Previous slide

Next slide

Back to first slide

View graphic version