Section 5.2 Further Recurrence Relations

This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Geberalizing the inequality from the previous section gives us: T(n) ⇐ qT(n/2) + cn when n > 2.

For more than 2 subproblems,