Class 27: More Recursive Algorithms

Held Tuesday, October 10, 2000

Summary

Today we continue our analysis of recursive algorithms.

Notes

• Are there questions on the current chapter of Bailey (the one on algorithm analysis)?
• You may want to start reading the chapter on sorting.
• Thursday's convocation: Will Talbert, Noyce Visiting Professor speaks on Studying the Origin of the Elements Using Radioactive Ion Beams. 11:00 in Harris.
  • Why do they put Physicists in Harris?
• This past weekend, I went to a marriage celebration for folks I knew in college (at the University of Chicago, another liberal arts institution). Almost everyone I know went into "IT" (even though they were economics, history, philosophy, ... majors).

Overview

• Solving recurrence relations
• Exponentiation
• Algorithm design with divide and conquer
• Fibonacci

A Quick Recap

• We've been analyzing the running time of recursive algorithms.
• Yesterday, we defined a function for the running time of our smallest algorithm with a pair of equations.

  f(1) = 2
  f(n) = 5 + 2*f(n/2)
  

• Let's once again look at how we might determine the pattern of this function.

  f(1) = 2
  f(2) = 5 + 2*f(1) = 5 + 2*2
  f(4) = 5 + 2*f(2) = 5 + 2*(5 + 2*2) = 3*5 + 4*2
  f(8) = 5 + 2*f(4) = 5 + 2*(3*5 + 4*2) = 7*5 + 8*2
  

• Do you see a pattern? I do

  f(n) = (n-1)*5 + n*2
  

• Is that the same pattern we worked out yesterday? It's similar.

  f(n) = 7*n - 5
  

Generalizing the Technique

• The technique we've used is a good one for analyzing the running time of recursive functions, so let's generalize.
• Here's how I think of it:
  • Start by defining a function, f, that represents the running time of your method.
  • Determine the value of f for the base cases.
  • Determine the value of f for the recursive cases. This will normally be a recursive function definition
  • Build up from small parameters to large parameters.
  • Eventually, you should see a pattern, so generalize.
  • Check your pattern.
• Note that it may also work to build down from large parameters to small parameters.
• How do you see the patterns? Mostly practice and luck.

Running Times

Just to give you a sense of running times, here's a short table.

N     O(1)    O(log2N)    O(N)    O(Nlog2N)    O(N2)    O(2N)

   1   1        0          1          1          1         2

   2   1        1          2          2          4         4

   4   1        2          4          8         16        16

   8   1        3          8         24         64       256

1000   1       10       1000     10,000  1,000,000      10300

8000   1       13       8000    100,000 64,000,000      a lot

Exponentiation

• There are a number of techniques one can use for computing xⁿ, where n is an integer.
  • Complicated mathematics
  • Multiply x*x*x*...*x n times
  • Divide and conquer
• Although our algorithms will admit negative exponents, our analyses will assume positive exponents.
• As we observed, there are two techniques for doing the repeated multiplication: we can use iteration or recursion.
• Let's consider each function

  
  /**
   * An illustration of different mechanisms for computing x^n.
   *
   * @author Samuel A. Rebelsky
   * @version 1.0 of October 1999
   */
  public class Exponentiation {
  
    // +---------+-------------------------------------------------
    // | Methods |
    // +---------+
  
    /**
     * Compute x^n by multiplying x*x*...*x n times.  Uses
     * iteration as the mechanism for repetition.
     */
    public static double expA(double x, int n) {
      // Handle negative exponents.  x^(-n) = 1/(x^n)
      if (n < 0) {
        return 1/expA(x,-n);
      }
      // Prepare to compute the product.
      double product = 1;
      // Multiply by each x.  (Note that 1*x*x*...*x = x*x*...*x.)
      for (int i = 0; i < n; ++i) {
        product = product * x;
      } // for
      // That's it, we're done.
      return product;
    } // expA(double,int)  
  
    /**
     * Compute x^n by multiplying x*x*...*x n times.  Uses
     * recursion as the mechanism for repetition.
     */
    public static double expB(double x, int n) {
      // Handle negative exponents.  x^(-n) = 1/(x^n)
      if (n < 0) {
        return 1/expB(x,-n);
      } // if (n < 0)
      // Base case: x^0 is 1.
      if (n == 0) {
        return 1;
      } // if (n == 0)
      // Recursive case: x*x*...*x = x*(x*...*x)
      // That is: x^n = x*(x^(n-1))
      else {
        return x * expB(x, n-1);
      } // Recursive case, if (n > 0)
    } // expB(double,int)  
  
    /**
     * Compute x^n by a recursive divide-and-conquer algorithm.
     */
    public static double expC(double x, int n) {
      // Handle negative exponents.  x^(-n) = 1/(x^n)
      if (n < 0) {
        return 1/expB(x,-n);
      } // if (n < 0)
  
      // Base case: x^0 is 1.
      if (n == 0) {
        return 1;
      } // Base case: n == 0
  
      // Recursive case (when n is odd)
      //   x*x*...*x = x*(x*...*x)
      //   That is: x^n = x*(x^(n-1))
      else if (n % 2 == 1) {
       return x * expC(x,n-1);
      } // Recursive case (when n is odd)
  
      // Recursive case (when n is even)
      //   Let n be 2k
      //   x^n = x^(2k) = x^k * x^k
      else {
        int k = n/2;
        double tmp = expC(x,k);
        return tmp*tmp;
      } // Recursive case (when n is even)
    } // expC
  } // class Exponentiation
  
  
  

Repeated Multiplication with Iteration

• The first version, expA, is perhaps the easiest to analyze.
• There is some preparatory work. That takes a constant number of steps. We'll call that a₁.
• There is a loop that is repeated n times.
  • Each time through the loop, a constant number of steps are done. We'll call that a₂.
• After the loop, a few more steps are done (okay, just a return). We'll call that a₃.
• What's the approximate running time?
  • a₁ + a₂*n + a₃
• Using Big-O notation, we can throw away the constants and get O(n).

Repeated Multiplication with Recursion

• The second version, expB, is somewhat more difficult to analyze because of the recursion.
• Here are the basic steps
  • exp(x,0) is 1
  • exp(x,n) is x * exp(x, n-1)
• But how do we analyze the running time of this algorithm?
• One technique that is typically fruitful (although somewhat mathematical), is to define a function, f_b(n), that represents the the number of steps the algorithm takes on input of size n.
• What can we say about this function?
• We know that when n is 0, the function takes a constant number of steps.
  • f_b(0) = b₁
• When n is greater than 0, the function takes some constant number of steps before and after the recursive call plus the time for the recursive call.
  • We'll call the constant extra steps b₂
• How do we determine the number of steps for the recursive call (expB(x,n-1))? Hmmm ... Wait! f_b is supposed to tell us that!
  • f_b(n) = b₂ + f_b(n-1)
• We've defined the running time recursively, too. That doesn't help us much if we want to do some Big-O analysis. So let's figure out what f_b really is.
• Let's start by repeatedly applying our recursive rule ...
  • f_b(n) i+ = b₂ + f_b(n-1)
  • = b₂ + b₂ + f_b(n-2)
  • = b₂ + b₂ + b₂ + f_b(n-3)
• We might then generalize
  • f_b(n) = k*b₂ + f_b(n-k)
• Can we ever get rid of the recursive term? Yes! When n = k, n-k is 0, and we know the value of f_b(0).
  • f_b(n) = n*b₂ + b₁
• As you might be able to tell, that's just O(n).

Detour: Algorithm Design: Divide and Conquer

• As you may have noted, binary search is much faster than sequential search.
• How did we make binary search run faster? We took a particular approach to the data:
  • We broke the input into half
  • We recursed on one half.
• The idea of breaking the input in half will be useful in developing algorithms to solve a variety of problems. It is a key part of your ``programmer's toolbox''. Make sure to consider whether it is appropriate each time you visit a problem.

Exponentiation with Divide and Conquer

• Can we use divide-and conquer to solve the exponentiation problem (or to improve our solution)?
• What can we divide in half? (What gives the ``size'' of the problem?)
• Here's another version of exponentiation, based on a divide-and-conquer strategy.

    /**
     * Compute x^n by a recursive divide-and-conquer algorithm.
     */
    public static double expC(double x, int n) {
      // Handle negative exponents.  x^(-n) = 1/(x^n)
      if (n < 0) {
        return 1/expB(x,-n);
      } // if (n < 0)
  
      // Base case: x^0 is 1.
      if (n == 0) {
        return 1;
      } // Base case: n == 0
  
      // Recursive case (when n is odd)
      //   x*x*...*x = x*(x*...*x)
      //   That is: x^n = x*(x^(n-1))
      else if (n % 2 == 1) {
       return x * expC(x,n-1);
      } // Recursive case (when n is odd)
  
      // Recursive case (when n is even)
      //   Let n be 2k
      //   x^n = x^(2k) = x^k * x^k
      else {
        int k = n/2;
        double tmp = expC(x,k);
        return tmp*tmp;
      } // Recursive case (when n is even)
    } // expC
  

• We'll use the same technique of ``define a function whose value is the number of steps the algorithm takes''. This time, we'll call the function f<sub>c</sub>.
• This time, life is a little harder because we have two different recursive cases. (Odd and Even).
  • Fortunately, the odd case transforms into the even case. That is, if n is odd, then on the next recursive call it will be even.
  • In effect, by choosing a bigger value for the ``constant'' work, we can pretend that n is divided by two in each recursive call.
  • If it makes it easier, think about replacing the lines that read

        else if (n % 2 == 1) {
         return x * expC(x,n-1);
        } // Recursive case (when n is odd)
    

    with

        else if (n % 2 == 1) {
          double tmp = expC(x, (n-1)/2);
          return x * tmp * tmp;
        } // Recursive case (when n is odd)
    

• So
  • f_c(0) = c₁
  • f_c(1) = c₂
  • f_c(n) = c₃ + f_c(n/2)
• What function is this? Again, we will try some analysis by hand to figure it out.
• A few applications of the recursive rule
  • f_c(n)
  • = c₃ + f_c(n/2)
  • = c₃ + c₃ + f_c(n/4)
  • = c₃ + c₃ + c₃ + f_c(n/8)
• Can we generalize? Certainly.
  • f_c(n) = k*c₃ + f_c(n/2^k)
• When can we get rid of the recursive term? When n/2^k is 1.
  • That is, k is ``the power to which you must raise 2 in order to get n''.
  • Fortunately, there's a name for that value. We call it log₂(n).
• Hence,
  • f_c(n) = log₂(n)*c₃ + c₂
• That is, this algorithm is an O(log₂(n)) algorithm.

Fibonacci

• We can compute Fibonacci numbers
  • iteratively, starting at the bottom and working our way up
  • recursively, using the rule that fib(n) = fib(n-1) + fib(n-2)
• The iterative Fibonacci calculation is fairly easy to analyze. Since we step through n different Fibonacci numbers and do a constant amount of calculation for each, that algorithm is O(n).
• The recursive version is much harder. Again, we'll use a function to represent the number of steps the algorithm takes on input of size n. We'll just call this function f.
• Two base cases:
  • f(0) = d₁
  • f(1) = d₂
• One recursive case
  • f(n) = d₃ + f(n-1) + f(n-2)
• Hmmm ... this is surprisingly similar to the function that defines Fibonacci.
  • Thus, the number of steps to compute the nth Fibonacci number is more than the value of the nth Fibonacci number.
• This function grows fairly quickly, but how quickly?
  • We'll ignore the d₃ to make our life easier. (No, you can't always do so, but it seems safe in this case.)
• We'll take advantage of the observation that f(n-2) <= f(n-1)
  • While the observation is fairly obvious, the decision to use it is not. You should not expect to have come up with it on your own.
• So, let's try applying that observation
  • f(n) = f(n-1) + f(n-2)
  • f(n) <= f(n-1) + f(n-1)
  • f(n) <= 2*f(n-1)
• Okay, now we can try applying that rule a few times.
  • f(n) <= 2*f(n-1)
  • f(n) <= 2*2*f(n-2)
  • f(n) <= 2*2*2*f(n-3)
• Can we generalize? Sure
  • f(n) <= 2^k*f(n-k)
• Does this lead to a natural answer. Let k = n.
  • f(n) <= 2ⁿ*d₁
• f(n) is in O(2ⁿ)
  • This may be painfully slow (as you've seen)
• But this is an upper bound, and it may be much too large. Let's try a lower bound.
• Again, we'll use the relationship between f(n-1) and f(n-2), but in the opposite direction.
  • f(n) = f(n-1) + f(n-2)
  • f(n) >= f(n-2) + f(n-2)
  • f(n) >= 2*f(n-2)
• We can now apply that rule a few times
  • f(n) >= 2*f(n-2)
  • f(n) >= 2*2*f(n-4)
  • f(n) >= 2*2*2*f(n-6)
• Generalizing,
  • f(n) >= 2^k*f(n-2k)
• When k = n/2, we're done
  • f(n) >= 2^(n/2)*d₁
• This is a lower bound, rather than an upper bound. Hence, we cannot use Big-O. Instead, we use little-o for lower bound.
  • f(n) is in o(2^(n/2)).
• This is still painfully slow.