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

In this section we apply some divide and conquer algorithms to solve the problem of counting inversions. It is similar to merge sort. This problem is about matching preferences etc.