Recurrence Relations

Videos

Readings

  • These slides on MergeSort by Goodrich and Tamassia might be useful if you want to learn more about how MergeSort actually works, in addition to knowing a proof about its runtime.

Warmup

Problem 1

Here is a description of the binary search algorithm. Binary search is a recursive algorithm for determining whether an item \(x\) is in a list \(L\). We’ll assume that both \(x\) and all the elements of \(L\) are integers. We also assume that \(L\) contains at least one element and is sorted in ascending order. Let \(L_i\) be the \(i\)th element of \(L\).

Algorithm: \(\mathrm{BinarySearch}\):

  1. If \(L\) has length 1, then check whether \(L_1 = x\). If so, return \(\mathbf{True}\).
  2. Otherwise, divide \(L\) into two equal-length lists, \(L_1\) and \(L_2\). Let the final elements of these lists be \(\ell_1\) and \(\ell_2\), respectively.
    1. If \(x \leq \ell_1\), then return \(\mathrm{BinarySearch}\)(\(L_1\), \(x\)).
    2. Else, return \(\mathrm{BinarySearch}\)(\(L_2\), \(x\)).

Part A

Write an inductive proof that \(\mathrm{BinarySearch}\) works correctly. That is, prove that \(\mathrm{BinarySearch}\)(\(L\), \(x\)) returns \(\mathbf{True}\) if and only if \(x\) is in \(L\) for any list of length \(n \geq 1\).

Part B

Assume that the length of \(L\) is \(n = 2^p\) for some integer \(k \geq 0\), and let \(f(n)\) be the number of times it is required to compare \(x\) to an element of \(L\). Determine the number of steps required to run \(\mathrm{BinarySearch}\) on \(L\), assuming that \(x\) is not actually in \(L\) (this is an example of a “worst case” analysis). Write a recurrence relation for \(f(n)\) in the form

\[ \begin{aligned} f(n) = a f(n/b) + g(n), \end{aligned} \]

determining the values of \(a\) and \(b\) and the functional form of \(g(n)\).

Part C

The solution to your recurrence relation in the previous part has the form \(f(n) = x\log_y n + z\) for some constants \(x\), \(y\), and \(z\). Determine the values of each of these constants.

Hint: \(f(n) = f(n/2) + 1 = f(n/4) + 1 + 1 = \ldots\).

Part D

Write a careful proof by induction that your formula for \(f(n)\) solves the recurrence relation in Part B (under the assumption that \(n = 2^p\) for some integer \(p\geq 0\)).



© Phil Chodrow, 2024