$ $

Example: Binary Search

• Here is a useful example of recursion:

  public static int binarySearch(int[] values, int target, 
                                 int start, int end) {
  
      if (start > end) {
          return -1;
      }
  
      int mid = (start + end) / 2;
  
      if (target == values[mid]) {
          return mid;
      } else if (target < values[mid]) {
          return binarySearch(values, target, start, mid - 1);
      } else {
          return binarySearch(values, target, mid + 1, end);
      }
  
  }

Informal Analysis of Binary Search

• Informally, we could just try some searches and see show long they take:

• Result:

  \(n\)	total equality checks
  1	1
  2	2
  4	3
  8	4

• Looks like \(\log_2 n + 1\)

• (For non-powers-of-two \(\lfloor\log_2 n\rfloor + 1\))

Binary Search Recurrence

• Initial conditions:

  \(W(1) =\) ??

• \(W(1) = 1\)

• Recurrence:

  \(W(n) = ??\)

• \(W(n) = 1 + W(n/2)\)

Example: Recursive Binary Search

• Worst-case recurrence:

  \(W(1) = 1\)

  \(W(n) = 1 + W(n/2)\)

Example: Recursive Binary Search

• Worst-case recurrence:

  \(W(1) = 1\)

  \(W(n) = 1 + W(n/2)\)

• We can use backward substitution to calcuate the value of the recurrence at particular values of \(n\):
  • \(W(8) = ?\)
  • \(W(8) = 1 + W(4)\)
  • \(W(8) = 1 + (1 + W(2))\)
  • \(W(8) = 1 + (1 + (1 + W(1)))\)
  • \(W(8) = 4\)

Example: Recursive Binary Search

Step 2: Backward Substitution

\(W(1) = 1\)

\(W(x) = 1 + W(x/2)\)

\(W(n)\)	\(=1 + W(n/2)\)
	\(=1 + 1 + W( (n/2)/2 )\)	(substitute)
	\(=2 + W(n/4)\)	(simplify)
	\(=2 + 1 + W( (n/4)/2 )\)	(substitute)
	\(=3 + W(n/8)\)	(simplify)
	\(...\)
	\(=i + W(\frac{n}{2^i})\)	(generalize)

Solve for \(i\) that results in initial condition:

\(\frac{n}{2^i} = 1\)

\(n = 2^i\)

\(i = \log_2 n\)

Substitute \(\log_2 n\) for \(i\):

\(W(n) = \log_2 n + 1\)

Step 3: Check the Answer

Applying recurrence:

\(W(1) = 1\)

\(W(2) = 1 + W(1) = 1 + 1 = 2\)

\(W(4) = 1 + W(2) = 1 + 2 = 3\)

Applying solution:

\(W(1) = \log_2 1 + 1 = 0 + 1 = 1\)

\(W(2) = \log_2 2 + 1 = 1 + 1 = 2\)

\(W(4) = \log_4 4 + 1 = 2 + 1 = 3\)

Steps to Analyzing a Recursive Algorithm

• Step 1: Develop a Recurrence (Last time)
• Step 2: Solving the Recurrence
  • One approach is the method of backward substitution:
    1. Expand the recurrence by repeated substitution until a pattern emerges.
    2. Characterize the pattern by expressing the recurrence in terms of \(n\) and \(i\), (where \(i\) is the number of substitutions).
    3. Substitute for \(i\) an expression that will remove the recursive term.
    4. Manipulate the result to achieve a closed-form solution.
• Step 3: Check Your Answer
  • Make sure that the recurrence and the closed form solution agree for several values of \(n\).

Another Example:

count the comparison values[start] == values[end]

    public static boolean unique(int[] values, int start, int end) {
        if (start >= end) {
            return true;
        } else if (values[start] == values[end]) {
            return false;
        } else {
            return unique(values, start, end - 1) 
                    && unique(values, start + 1, end);
        }

    }

Part 1:

    public static boolean unique(int[] values, int start, int end) {
        if (start >= end) {
            return true;
        } else if (values[start] == values[end]) {
            return false;
        } else {
            return unique(values, start, end - 1) 
                    && unique(values, start + 1, end);
        }

    }

\(W(1) = \color{orange}{0}\)

\(W(n) = \color{red}{1} + \color{green}{2W(n-1)}\)

Part 2:

\(W(1) = 0\)

\(W(x) = 1 + 2W(x-1)\)

\(W(n)\)	\(=1 + 2W(n - 1)\)
	\(=1 + 2(1 + 2W((n-1)-1 )\)	(substitute)
	\(=1 + 2 + 4W(n - 2)\)	(simplify)
	\(=1 + 2 + 4(1 + 2W((n-2) - 1 )\)	(substitute)
	\(=1 + 2 + 4 + 8W(n - 3)\)	(simplify)
	\(...\)
	\(=\sum_{j=0}^{i-1}2^j + 2^iW(n-i)\)	(generalize)
	\(=2^i - 1 + 2^iW(n-i)\)	(generalize)

Solve for \(i\) that results in initial condition:

\(n - i = 1\)

\(i = n -1\)

Substitute \(n - 1\) for \(i\):

\(W(n) = 2^{n-1} - 1 + 2^{n-1}\times 0 = 2^{n-1} - 1\)

Part 3

Applying recurrence:

\(W(1) = 0\)

\(W(2) = 1 + 2W(0) = 1 + 0 = 1\)

\(W(3) = 1 + 2W(1) = 1 + 1 = 2\)

\(W(4) = 1 + 2W(2) = 1 + 2 = 3\)

Applying solution:

\(W(1) = 2^{1-1} - 1 = 0\)

\(W(2) = 2^{2-1} - 1 = 1\)

\(W(3) = 2^{3-1} - 1 = 3\)