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…

• 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
• 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.
• there are log₂n levels of recursion
• to sum all of the work at these levels is a geometric sum with powers r=q/2
• we apply a formula for a geometric sum

(5.4) Any function with the form T(n) =< qT(n/2) + cn is bounded by O(n^log₂q).