Recursion Tree, Solving Recurrence Equations

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?

-
Oh I forgot the master theorem, which cant be applied to all the recurrence equations – DarthVader Oct 6 '09 at 2:09

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.

-
Cool. Thanks. I will try that. – DarthVader Oct 6 '09 at 2:12

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%5Fseries

Generating functions are also extremely useful in probability.

-
The text passage discusses methods for solving recurrence equations, specifically focusing on the substitution method and the use of recurrence trees for generating guesses. It also mentions the master theorem and generating functions as additional tools.
no_question

the passage does not contain a specific mathematical question or calculation that requires an answer. it is more of a discussion or explanation of different methods for solving recurrence equations.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Recursion Tree, Solving Recurrence Equations

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?

-
Oh I forgot the master theorem, which cant be applied to all the recurrence equations – DarthVader Oct 6 '09 at 2:09

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.

-
Cool. Thanks. I will try that. – DarthVader Oct 6 '09 at 2:12

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%5Fseries

Generating functions are also extremely useful in probability.

-
user
The text passage discusses methods for solving recurrence equations, specifically focusing on the substitution method and the use of recurrence trees for generating guesses. It also mentions the master theorem and generating functions as additional tools.

TYPE: NO_QUESTION

The passage does not contain a specific mathematical question or calculation that requires an answer. It is more of a discussion or explanation of different methods for solving recurrence equations.