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 calls.
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.
- Identifying a pattern:
At any given level j, we have q^j distinct problems, each of size n/(2^j).
Thus the total time at any level j is (q^j)(cn/(2^j))= [(q/2)^j]*cn
- Summing over all levels of recursion:
There are log(in base 2)(n)levels of recursion.
After some calculations, we find that the overall running time is:
T(n) = O([n^(log(in base 2) q)])
So,the generalization is:
Any T(.) that satisfies the recurrence relation we cited in the beginning paragraph with q>2 is bounded by O(n^(log(in base2)q)).
Applying Partial Substitution
We can find the the same bound using the substitution method as follows:
We suppose T(n) ≤ qT(n/2) + cn and prove that we still get the same bound. See Book page 215-16 for complete proof.
The Case of One Subproblem:
For q = 1, the total work spent on each level decreases as we run our recursion algorithm. After unrolling the algorithm, we find that in this case:
Any T(.) satisfying the recurrence relation defined in the beginning paragraph of this section with q = 1 is bounded by O(n).
A Related Recurrence: T(n) ≤ 2T(n/2) + O(n²)
On this class of problems, we spending O(n²) in recombining and divisions. After unrolling the recurrence relations, we find that:
T(n) ≤ O(n²).
I give this section 7/10
