9.8.1 Result 1: Lower Bound on Worst Case Complexity

• Given a list of n distinct elements, there are n! possible outcomes that represent correct sorted orders.


$\Downarrow$

 
• any decision tree describing a correct sorting algorithm on a list of n elements will have at least n! leaves.
• In fact, if we delete nodes corresponding to unnecessary comparisons and if we delete leaves that correspond to an inconsistent sequence of comparison results, there will be exactly n! leaves.
The length of a path from the root to a leaf gives the number of comparisons made when the ordering represented by that leaf is the sorted order for a given input list L.
• The worst case complexity of an algorithm is given by the length of the longest path in the associated decision tree.
• To obtain a lower bound on the worst case complexity of sorting algorithm, we have to consider all possible decision trees having n! leaves and take the minimum longest path.

In any decision tree, it is clear that the longest path will have a length of at least log n!

Since

$$\sim \left(\vphantom{\frac{n}{e}}\right. {\frac{n}{e}} \left.\vphantom{\frac{n}{e}}\right)^{n}_{}$$ n!

$$\sim$$ log n! nlog n

More Precisely,

$$\geq \left(\vphantom{\frac{n}{2}}\right. {\frac{n}{2}} \left.\vphantom{\frac{n}{2}}\right)^{\frac{n}{2}}_{}$$ n!

$$\geq {\frac{n}{2}} {\frac{n}{2}}$$ or log(n!)

$${\frac{n}{2}} {\frac{n}{2}}$$ =

Thus any sorting algorithm that only uses comparisons has a worst case complexity

                                                                                                                                     $$\Omega$$(nlog n)