Recursion and Recurrence Relations

Merge Sort

• Our final example of recursion will be to sort. Recall we have seen two sorting algorithms, both of which were \(O(n^2)\).
• our next algorithm will be like binary search in that it is recursive by definition. It is called merge sort.
• The basic idea to to take the array, divide it in half, sort each half, and then merge the two halves together. It turns out that merging two already sorted list can be done in linear time:

  def merge(left, right):
      merged = []
      left_index = 0
      right_index = 0
      
      # Merge the two halves in sorted order
      while left_index < len(left) and right_index < len(right):
          if left[left_index] <= right[right_index]:
              merged.append(left[left_index])
              left_index += 1
          else:
              merged.append(right[right_index])
              right_index += 1
      
      # Append any remaining elements
      merged.extend(left[left_index:])
      merged.extend(right[right_index:])
      
      return merged
  

• You just walk down each list, adding the smaller element to the result.
• Now, actual merge sort is easy. It is exactly as I described:

  def merge_sort(arr):
      if len(arr) <= 1:
          return arr
      # Divide the array into two halves
      mid = len(arr) // 2
      left_half = arr[:mid]
      right_half = arr[mid:]
      # Recursively sort the two halves
      left_half = merge_sort(left_half)
      right_half = merge_sort(right_half)
      # Merge the sorted halves
      return merge(left_half, right_half)
  

• Take a minute and sort eight numbers to see how that works
• Now that we have a new, recursive, sort algorithm, the next thing we need to do is figure out how long it takes. I like to do that with a picture:
  
• What we see here is all the work being done in all the calls and merges. each row is the array split in to the correct number of sub-arrays at that depth of the recursion. Note the arlgorithm does not work in that order, it completes everything on the left side before doing any work on the right, but we will analyze by levels.
• If we have n elements, we know that repeatedly dividing by 2 will give us \(\lg n\) rows. In each row there are n elements that need merging, so there is n work per row. That means the total work of merging is \(O(n\lg n)\).
• Now, for counting the calls we have increasing number of calls, going up to n calls in the \(\lg n\)th line. We can write this as: \[\sum_{i=1}^{\lg n} 2^{i}\]
• If you weren't asleep in calculus you'd remember that there is a formula for geometric seies is: \[ \sum_{i=0}^{n} a2^{i} = \frac{a(1-r^n)}{1-r} -1 \]
• For us, a is 1 and n is really \(\lg n\), so plugging in, we get: \[ \sum_{i=1}^{\lg n} 2^{i} = \frac{1-2^{\lg n}}{1-2}\\ = 2^{\lg n} -2\\ = n-2, \text{ or}\\ \in O(n) \]
• Putting this all together, we get \(O(n)\) calls, plus \(O(n\lg n)\) work in the merges, for a total runtime of \(O(n \lg n)\).
• Recurrence relations
  1. Not every recursive algorithm is to amenable to the "draw layers" analysis we just did. Recurrence relations are a more general way to find the big O of a recursive function.
  2. We start by define a function that takes the size of the input \(n\) and outputs the big O of the recursion. We call that \(T(n)\) (it's tradition)
  3. Recall we agreed that the big O of merge in mergesort is \(O(n)\). Thus we can define for mergesort: \[T(n) = T(\frac{1}{2}n) + T(\frac{1}{2}n) + O(n)\] To make the whole recurrence relation complete (we need the base case) it is: \[\begin{align} T(0) &= O(1)\\ T(1) &= O(1)\\ T(n) &= T(\lfloor\frac{n}{2}\rfloor ) + T(\lceil \frac{n}{2}\rceil ) + O(n) \end{align}\]
  4. We will attack this thing with the unrolling/iteration method; \[\begin{align} T(n) &\leq 2T(\frac{n}{2})+ cn\\ &\leq 2(2T(\frac{n}{4})+c\frac{n}{2})+cn\\ &\leq 4T( \frac{n}{4})+2cn\\ &\leq 4(2T\frac{n}{8}+c\frac{n}{4}) + 2cn\\ &\leq 8T\frac{n}{8}+3 cn\\ &\leq 2^kT\frac{n}{2^k} + kcn \end{align} \]
  5. how many times can we do this? Since we're dividing by 2, each time, it's \(\log n\), so plug that in: \[\begin{align} T(n) \leq& 2^{\lg n}T(\frac{n}{2^k}) + (\lg n)cn\\ \leq& nT(1) + c n\lg n\\ \leq& cn+cn\lg n\\ \in& O(n \lg n) \end{align} \]
  6. We will attack this thing with the unrolling/iteration method; \[\begin{align} T(n) &\leq 2T((\frac{n}{2})+ cn\\ &\leq 2(2T(\frac{n}{4})+c\frac{n}{2})+cn\\ &\leq 4T( \frac{n}{4})+2cn\\ &\leq 4(2T\frac{n}{8}+c\frac{n}{4}) + 2cn\\ &\leq 8T\frac{n}{8}+3 cn\\ &\leq 2^kT\frac{n}{2^k} + kcn \end{align} \]
  7. how many times can we do this? Since we're dividing by 2, each time, it's \(\log n\), so plug that in: \[\begin{align} T(n) \leq& 2^{\lg n}T(\frac{n}{2^k}) + (\lg n)cn\\ \leq& nT(1) + c n\lg n\\ \leq& cn+cn\lg n\\ \in& O(n \lg n) \end{align} \]