Chapter 5.2: Further Recurrence Relations
There is a more general class of algorithms obtained by considering divide and conquer algorithms that create recursive calls on q subproblems of size n/2 each and then combine the results in O(n) time. We treat the cases q > 2, q = 1, and q = 2 all separately.
The Case of q > 2 Subproblems
At the first level of recursion, we have a single problem of size n. At the next level, we have q problems, each of size n/2. The next level yields q^2 problems of size n/4 each, for a total time of (q^2/4)cn. We see that the total work per level is increasing as we proceed through the recursion. The total work performed at any level j is 1)