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

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. for a website like Netflix that compares your rankings and another person's rankings of a set of n movies. We order our ranking in order 1 to n and the other persons ranking according to our order and see how many are inverted. A complete agreement is when the rankings are in ascending order. A complete disagreement is when the rankings are in descending order.

The Algorithm:

• if we looked at every pair of number to see if they were inverted would take O(n² time
• our goal is O(n log n)
• divide the set of numbers into two pieces of size n/2 and count inversions in each half separate then count the inversions between the halves
• to count which numbers belong in the other half we recursively sort the halves
• after recursively sorting and counting inversions to each half apply Merge-and-Count
  • we should produce a single sorted list of the union of the two halves
  • also should produce the number of inversions between the two lists
  • have 2 pointers that point to the current element in each list
  • idea is to append the smallest element to the union list, and if the 2nd half at the pointer is smaller than the first half at that current pointer there is an inversion

 Merge-and-Count(A,B)
   Maintain a Current pointer into each list, initialized to point to the front elements
   Maintain a variable Count for the number of inversions, initialized to 0
   While both lists are nonempty:
     Let ai and bj be the elements pointed to by the current pointer
     append the smaller of these two to the output list
     if bj is the smaller element then 
       increment count by number of elements remaining in A
     endif
     advance the current pointer in the list from which the smaller element was selected
   Endwhile
   Once one list is empty, append the remainder of the other list to the output
   return count and the merged list
   

Analysis:

Everything happening in the while loop is constant O(1) time. The while loop executes at most n times so the run time of Merge-and-Count is O(n).

The merge and count function is used in another recursive algorithm sort-and-count

  Sort-and-Count(L)
    If the list has one element then
       there are no inversions
    Else
       Divide the list into two halves:
          A contains the first [n/2] elements
          B contains the remaining [n/2] elements
       (inversionsA, A) = Sort-and-Count(A)
       (inversionsB, B) = Sort-and-Count(B)
       (totalInversions, L) = Merge-and-Count(A,B)
    Endif
    Return totalInversions = inversionsA + inversionsB + totalInversions, and the sorted list L
    

The recurrence relation is T(n) =< 2T(n/2) + cn. This is O(n log n) time.

This section was very short and easy to read. No problems here. The pictures showed on the slides in class were especially helpful in understanding this section. Readability: 9/10

Finding the Closest Pair of Points