Proof – Sorting decisions (2)

• every leaf of the decision tree is a possible result of the sorting procedure

• as there are n! possible permutations for an n-element list, the tree must have at least n! leaves

• the worst case for an algorithm corresponds to the longest path in the tree