$ T(n) \leq c n + T\left( \lceil n/2 \rceil \right) + T\left( \lfloor n/2 \rfloor \right) $We also showed that a simplified version of this recurrence was $O(n \lg n)$, which we took as a hypothesis about the real recurrence. This class, by a long, exhaustive derivation, we verified that hypothesis. I.e. we showed that MergeSort's worst case running time is $O(n \lg n)$.
Normally, our next step would be to analyze things to determine a lower-bound on the worst case running time. However, I decided we'd do something more ambitious, that is ...
One of the things that makes analyzing algorithms difficult, is that they are dynamic. An algorithm's state changes over the period of time in which it runs. However, it is possible with these sorting algorithms to talk about the algorithm as a static object, separated from any particular run of the algorithm. We saw how with an example. I showed in class how to construct the tree $T_3$ showing all possible ways insertion sort can run on a three element array.
One very interesting feature of this tree is that the worst-case running time for insertion-sort on three elements is given by the height of the tree. This will be important next class! Another important thing to note is the leaves. These represent the final order resulting from a run of insertion sort. You'll notice that all 3! permutations of x,y,z appear as leaves. This is in fact necessary, since there needs to be at least one path that gets you to each permuation, since any ordering is possible as input.
The key observation is that a sorting algorithm like insertion sort can be characterized by an infinite sequence of such trees: one for each input size.