$ $

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)$

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)$

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$