This includes algorithms like Merge sort and Insertion sort.
Assume we’re given a correct sorting algorithm. It’s a black box to us, but we want to show to show that its runtime cannot be .
Comparison based model: when talking about arrays and runtime, we access the input array via comparisons. For example, is ?
Decision tree: a rooted binary tree. Labels on nodes and edges. Nodes ask a question, and edges are outputs/answers. Labels on the edges have to be unique.
Use the decision tree to show that the worst case number of comparisons (aka one execution possibility) is . In other words, the depth/height of the tree is .
If the algorithm is correct, how many leaves must exist in the decision tree? The number of leaves must be , where . We’re permutating here.
Each leaf corresponds to a potential output of the algorithm, after it makes a decision. Therefore, there are ways to place elements.
Since leaves , we have , and so the height .