CSC 378: Data Structures and Algorithm Analysis
ANALYSIS OF RECURSIVE PROGRAMS
[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.
Also see "Recursion Trees" in [CLR 4.2].