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
• total work per level is increasing
• 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) when q > 2.

When q = 1…

• level one: single problem size n takes cn time plus time in subsequent recursive calls
• level two: problem size n/2 with cn/2 time
• next level: problem size n/4 with cn/4 time
• total work per level is decreasing
• the pattern: each level has size n/2^j with running time cn/2^j
• there are log₂n levels of recursion
• the geometric sum

(5.5) Any function with the form T(n) =< qT(n/2) + cn is bounded by O(n) when q = 1.

Another Recurrence: T(n) =< 2T(n/2) + O(n²)

Counting Inversions

Finding the Closest Pair of Points