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 .