Recursion Tree, Solving Recurrence Equations

Question

As far as I know There are 4 ways to solve recurrence equations : 1- Recursion trees 2- Substitution 3 - Iteration 4 - Derivative

We are asked to use Substitution, which we will need to guess a formula for output. I read from CLRS book that there is no magic to do this, i was curious if there are any heuristics to do this?

I can certainly have an idea by drawing a recurrence tree or using iteration but, because the output will be in Big-OH or Theta format, formulas doesnt necessarily match.

Does any one have any recommendation for solving recurrence equations using substitution?

Answer 1

For simple ones, just take a "reasonable" guess.

For more complicated ones, I would go ahead and use a recurrence tree — it seems to me to be the easiest "algorithm" for generating a guess. Note that it can be difficult to use a recurrence tree to prove a bound (the details are tough to get right). Recurrence trees are highly useful for forming guesses which are then proven by substitution.

I'm not sure why you're saying the formulas won't match with the output in Big-O or Theta. They typically don't match exactly, but that's part of the point of Big-O. Part of the trick of going back to substitution is knowing how to plug in the Big-O solution to to make the substitution algebra work out. IIRC, CLRS does work out an example or two of this.

Answer 2

Please note that the list of possible ways to solve recurrence equations is definitely not complete, its merely a set of tools they teach Computer Scientists, because they will most likely solve most of your problems.

For exact solutions of recurrence equations mathematicians use a tool called generating functions. Generating functions give you exact solutions, and in general are more powerful than the master theorem.

There is a great resource online to learn about the here. http://www.math.upenn.edu/~wilf/DownldGF.html

If you go through the first couple examples you should get the hang of it in no time.

You need some math background and understand rudimentary taylor series. http://en.wikipedia.org/wiki/Taylor_series

Generating functions are also extremely useful in probability.