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 $o(ngn)$.

**Comparison based model:** when talking about arrays and runtime, we access the input array $A[1..n]$ via comparisons. For example, is $A[i]≥A[j]$?

**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 $Ω(ngn)$. In other words, the depth/height of the tree is $ngn$.

If the algorithm is correct, how many leaves must exist in the decision tree? The number of leaves must be $≥n!$, where $∣A∣=n$. We’re permutating $A$ here.

Each leaf corresponds to a potential output of the algorithm, after it makes a decision. Therefore, there are $n!$ ways to place $n$ elements.

Since leaves $≤2_{h}$, we have $(2n )_{2n}≥n!$, and so the height $h≥2n g(2n )$.