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.

def pow1(x, y):
    if y == 0:
        return 1
    else:
        return x * pow1(x, y-1)

def pow2(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x
    elif y % 2 == 0:
        return pow2(x, y/2) * pow2(x, y/2)
    else:
        return 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.