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}\), and return \(\mathbf{False}\) if not.
  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\)).

Throughout this problem, we assume that the list \(L\) has length which is always either 1 or even. This corresponds to assuming that the length of \(L\) is a power of 2, which will make the analysis easier. It is possible to not use these assumptions, at the cost of more complex code and mathematical analysis.

Part A

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

Part B

Assume that the length of \(L\) is \(n = 2^p\) for some integer \(p \geq 0\), and let \(f(n)\) be the number of times it is required to compare \(x\) to an element of \(L\). We’d like to determine the number of steps required to run \(\mathrm{BinarySearch}\) on \(L\). To do this, start by writing 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, 2025