5.2 Further Recurrence Relations

In this section, we are concerned with the generalization of the recurrence relation we saw in the previous section. Indeed, we need to study the cases where we have an algorithm that makes recursive calls on q subproblems of size n/2 and combine the results in O(n) time.
So, the generalized recurrence relation is: T(n) ≤ qT(n/2) + cn for n > 2, and T(2) ≤ 2.

The case of q>2 Subproblems:

• Analyzing the first few levels:
  

At the first level, we have a single problem of size n. Takes at most cn time + time spent in subsequent recursive class.

The following level has q problems, each of size n/2. Each of these problems costs at most cn/2 for a total of at most (q/2)*cn + time spent in subsequent recursive calls.

The next level has q² problems, each of size n/4. Each of these problems costs at most cn/2 for a total of at most (q²/4)*cn + time spent in subsequent recursive calls.

SO the total work per level is increasing as the algorithm is executed.