Further Recurrence Relations

This section focuses on solving recurrence relations more generally. We look at divide and conquer algorithms that have q recursive calls on subproblems of size n/2. This recurrence relation is represented as T(n) =< qT(n/2) + cn.

When q > 2…

• First few levels: level one has problem size n, level two has q problems of size n/2 that take at most cn/2 time to a total of (q/2)cn. The next level is n² of size n/4 to a total time of (q²/4)n
• The pattern: each level has q^j problems with size n/2^j with a total work at each level = (q/2)^jcn.