I know that this type of equations can be solved by many methods, but I want to use to use recurrence tree method to solve the equation.Can anyone show me how it is done by recurrence tree method?
Asked
Active
Viewed 242 times
4
-
3You should try first, then we can help you fix it – BlackBear May 31 '17 at 11:12
-
1isT(n) guaranteed to be non-negative ? – wildplasser May 31 '17 at 11:22
-
Possible duplicate of https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence – Codor May 31 '17 at 11:42
-
1Is there an anchor? Like `T(0)=0` and `T(1)=0`? – fafl May 31 '17 at 11:48
-
Possible duplicate of [Computational complexity of Fibonacci Sequence](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) – May 31 '17 at 11:55
1 Answers
3
Recursion trees are used to draw out the execution of a recursive algorithm. This recurrence you're describing is basically the same recurrence as the recursive Fibonacci algorithm, where this equation:
F(n) = F(n-1) + F(n-2)
is solved for recursively, using an algorithm like this:
int fib(int x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
return fib(x-1)+fib(x-2); //Does this recurrence look familiar?
}
Which produces this tree for input 5:
5
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / 1
/ \ 2
3 2 / \
/ \ / \ 1 0
/ \ / \
2 1 1 0
/ \
/ \
1 0
Above, I have drawn a very simple recurrence tree for the Fibonacci sequence. I simply plugged in the first number (5) and continued to produce a simple tree from it's subsequent recursive calls. You can see that the height of the tree is N and the branching factor is 2, so our upper bound must be O(2^n). You can generalize this to get the answer to your specific question and any other recurrences you want to find using this method.
Jayson Boubin
- 1,504
- 2
- 11
- 19