How to do recurrence relations?

Question

nSo we were taught about recurrence relations a day ago and we were given some codes to practice with:

int pow(int base, int n){

if (n == 0)

  return 1;

else if (n == 1)

  return base;

else if(n%2 == 0)

  return pow(base*base, n/2);

else

 return base * pow(base*base, n/2);

}

The farthest I've got to getting its closed form is T(n) = T(n/2^k) + 7k. I'm not sure how to go any further as the examples given to us were simple and does not help that much. How do you actually solve for the recurrence relation of this code?

Answer 1

Let us count only the multiplies in a call to pow, denoted as M(N), assuming they dominate the cost (a nowadays strongly invalid assumption).

By inspection of the code we see that:

M(0) = 0 (no multiply for N=0)

M(1) = 0 (no multiply for N=1)

M(N), N>1, N even = M(N/2) + 1 (for even N, recursive call after one multiply)

M(N), N>1, N odd = M(N/2) + 2 (for odd N, recursive call after one multiply, followed by a second multiply).

This recurrence is a bit complicated by the fact that it handles differently the even and odd integers. We will work around this by considering sequences of even or odd numbers only.

Let us first handle the case of N being a power of 2. If we iterate the formula, we get M(N) = M(N/2) + 1 = M(N/4) + 2 = M(N/8) + 3 = M(N/16) + 4. We easily spot the pattern M(N) = M(N/2^k) + k, so that the solution M(2^n) = n follows. We can write this as M(N) = Lg(N) (base 2 logarithm).

Similarly, N = 2^n-1 will always yield odd numbers after divisions by 2. We have M(2^n-1) = M(2^(n-1)-1) + 2 = M(2^(n-2)-1) + 4... = 2(n-1). Or M(N) = 2 Lg(N+1) - 2.

The exact solution for general N can be fairly involved but we can see that Lg(N) <= M(N) <= 2 Lg(N+1) - 2. Thus M(N) is O(Log(N)).