[CLR 4.2]

Here's an example in which we analyze MergeSort.

Given a list of length , what is MergeSort's running time, ?

Here's the analysis of the individual parts of MergeSort:

And here's how we fit it all together:

Therefore, .

Recursion stops when . How much recursion occurs? In the example above, we had the sequence:

The argument of was

Q: Recursion stops when . When does this happen?

A: When

So recursion stops after levels.

[CLR 4.2]

Also see "Recursion Trees" in [CLR 4.2].