How do I use Master theorem to describe recursion?

Question

Recently I have been studying recursion; how to write it, analyze it, etc. I have thought for a while that recurrence and recursion were the same thing, but some problems on recent homework assignments and quizzes have me thinking there are slight differences, that 'recurrence' is the way to describe a recursive program or function.

This has all been very Greek to me until recently, when I realized that there is something called the 'master theorem' used to write the 'recurrence' for problems or programs. I've been reading through the wikipedia page, but, as usual, things are worded in such a way that I don't really understand what it's talking about. I learn much better with examples.

So, a few questions: Lets say you are given this recurrence:

r(n) = 2*r(n-2) + r(n-1);
r(1) = r(2) = 1

Is this, in fact, in the form of the master theorem? If so, in words, what is it saying? If you were to be trying to write a small program or a tree of recursion based on this recurrence, what would that look like? Should I just try substituting numbers in, seeing a pattern, then writing pseudocode that could recursively create that pattern, or, since this may be in the form of the master theorem, is there a more straightforward, mathematical approach?

Now, lets say you were asked to find the recurrence, T(n), for the number of additions performed by the program created from the previous recurrence. I can see that the base case would probably be T(1) = T(2) = 0, but I'm not sure where to go from there.

Basically, I am asking how to go from a given recurrence to code, and the opposite. Since this looks like the master theorem, I'm wondering if there is a straightforward and mathematical way of going about it.

EDIT: Okay, I've looked through some of my past assignments to find another example of where I'm asked, 'to find the recurrence', which is the part of this question I'm having the post trouble with.

Recurrence that describes in the best way the number of addition operations in the following program fragment (when called with l == 1 and r == n)

int example(A, int l, int r) {
  if (l == r)
    return 2;
  return (A[l] + example(A, l+1, r);
}

Answer 1

A few years ago, Mohamad Akra and Louay Bazzi proved a result that generalizes the Master method -- it's almost always better. You really shouldn't be using the Master Theorem anymore...

See, for example, this writeup: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

Basically, get your recurrence to look like equation 1 in the paper, pick off the coefficients, and integrate the expression in Theorem 1.

Answer 2

Zachary:

Lets say you are given this recurrence:

r(n) = 2*r(n-2) + r(n-1); r(1) = r(2) = 1

Is this, in fact, in the form of the master theorem? If so, in words, what is it saying?

I think that what your recurrence relation is saying is that for function of "r" with "n" as its parameter (representing the total number of data sets you're inputting), whatever you get at the nth position of the data-set is the output of the n-1 th position plus twice whatever is the result of the n-2 th position, with no non-recursive work being done. When you try to solve a recurrence relation, you're trying to go about expressing it in a way that doesn't involve recursion.

However, I don't think that that is in the correct form for the Master Theorem Method. Your statement is a "second order linear recurrence relation with constant coefficients". Apparently, according to my old Discrete Math textbook, that's the form you need to have in order to solve the recurrence relation.

Here's the form that they give:

r(n) = a*r(n-1) + b*r(n-2) + f(n)

For 'a' and 'b' are some constants and f(n) is some function of n. In your statement, a = 1, b = 2, and f(n) = 0. Whenever, f(n) is equal to zero the recurrence relation is known as "homogenous". So, your expression is homogenous.

I don't think that you can solve a homogenous recurrence relation using the Master Method Theoerm because f(n) = 0. None of the cases for Master Method Theorem allow for that because n-to-the-power-of-anything can't equal zero. I could be wrong, because I'm not really an expert at this but I don't that it's possible to solve a homogenous recurrence relation using the Master Method.

I that that the way to solve a homogeneous recurrence relation is to go by 5 steps:

1) Form the characteristic equation, which is something of the form of:

x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0

If you've only got 2 recursive instances in your homogeneous recurrence relation then you only need to change your equation into the Quadratic Equation where

x^2 - a*x - b = 0

This is because a recurrence relation of the form of

r(n) = a*r(n-1) + b*r(n-2)

Can be re-written as

r(n) - a*r(n-1) - b*r(n-2) = 0

2) After your recurrence relation is rewritten as a characteristic equation, next find the roots (x[1] and x[2]) of the characteristic equation.

3) With your roots, your solution will now be one of the two forms:

if x[1]!=x[2]
    c[1]*x[1]^n + c[2]*x[2]^n
else
    c[1]*x[1]^n + n*c[2]*x[2]^n

for when n>2. 4) With the new form of your recursive solution, you use the initial conditions (r(1) and r(2)) to find c[1] and c[2]

Going with your example here's what we get:

1) r(n) = 1*r(n-1) + 2*r(n-2) => x^2 - x - 2 = 0

2) Solving for x

x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1)

    x[1] = ((-1 + 3)/2) = 1
    x[2] = ((-1 - 3)/2) = -2

3) Since x[1] != x[2], your solution has the form:

c[1](x[1])^n + c[2](x[2])^n

4) Now, use your initial conditions to find the two constants c[1] and c[2]:

c[1](1)^1 + c[2](-2)^1 = 1
c[1](1)^2 + c[2](-2)^2 = 1

Honestly, I'm not sure what your constants are in this situation, I stopped at this point. I guess you'd have to plug in numbers until you'd somehow got a value for both c[1] and c[2] which would both satisfy those two expressions. Either that or perform row reduction on a matrix C where C equals:

[ 1 1   | 1 ]
[ 1 2   | 1 ] 

Zachary:

Recurrence that describes in the best way the number of addition operations in the following program fragment (when called with l == 1 and r == n)

int example(A, int l, int r) {
  if (l == r)
    return 2;
  return (A[l] + example(A, l+1, r);
}

Here's the time complexity values for your given code for when r>l:

int example(A, int l, int r) {      =>  T(r) = 0
  if (l == r)               =>  T(r) = 1
    return 2;               =>  T(r) = 1
  return (A[l] + example(A, l+1, r);    =>  T(r) = 1 + T(r-(l+1))
}

Total:                      T(r) = 3 + T(r-(l+1))

Else, when r==l then T(r) = 2, because the if-statement and the return both require 1 step per execution.

Answer 3

Your method, written in code using a recursive function, would look like this:

function r(int n) 
{
  if (n == 2) return 1;
  if (n == 1) return 1;
  return 2 * r(n-2) + r(n-1);  // I guess we're assuming n > 2
}

I'm not sure what "recurrence" is, but a recursive function is simply one that calls itself.

Recursive functions need an escape clause (some non-recursive case - for example, "if n==1 return 1") to prevent a Stack Overflow error (i.e., the function gets called so much that the interpreter runs out of memory or other resources)