Recurrences

Problem: Recursive Counting

Now we'll try out hand at counting operations embedded in recursive functions. Recall that we use recurrence relations to capture these counts, mimicking the structure of the function. We then guess a closed-form solution to the recurrence and check it with an inductive proof.

In class, we analyzed a sorting example. In lab, we'll analyze two implementations of the power/exponentiation function.

(define pow1
  (lambda (x y)
    (if (zero? y)
        1
        (* x (pow1 x (- y 1))))))

(define pow2
  (lambda (x y)
    (cond
      [(zero? 0) 1]
      [(= y 1)   x]
      [(zero? (remainder y 2))
       (* (pow2 x (/ y 2)) (pow2 x (/ y 2)))]
      [else
       (* x (pow2 x (/ y 2)) (pow2 x (/ y 2)))])))

For each of pow1 and pow2:

1. Identify a critical operation to count.

2. Give a recurrence relation describing the number of critical operations the function performs as a function of the size of its input.

   (Hint: which of the two inputs to pow1 and pow2 contributes to its runtime?)

3. Guess a closed-form solution to these recurrences by using the substitution method.

   (Hint: for pow2 the following summation identity will be useful:

   $$\sum _{i=0}^n{2}^i=2^{n+1}-1.)$$

4. Check your closed-form solution with an inductive proof.

After completing this exercise, you may be surprised by the results! It turns out that there is an important optimization omitted from pow2. Based on your analysis, identify the optimization for pow2 necessary to obtain a sublinear count of critical operations.