Algorithm cost for recursive funtion

so I have some problem to determined algorithm cost of this program
1
2
3
4
5
6
7
8
9
  int rFibNum(int b, int b, int n){
	cout << rFibNum(2, 3, 5) << endl;
	if (n == 1)
		return a;
	else if (n == 2)
		return b;
	else
		return rFibNum(a, b, n-1) + rFibNum(a, b, n-2)
}


from what I know first run will be this

T(n)= T(n-1)+T(n-2)+2

but not sure what to do next so help.
Should line 1 be:
int rFibNum(int a, int b, int n) ?

I doubt that line 2 should be where it is. It probably should be in the calling function, for example main().
Last edited on
A Fibonacci sequence is a Jacobi sequence that always starts with 1 and 1. So you don't need those arguments 'a' and 'b'. Just 'n'.

In any case, you should notice that to solve F(n-1) and F(n-2), both must solve F(n-3). You can see that each recurrence explodes like a mushroom cloud -- it's exponential.

T(n)=T(n-1)+T(n-2)+2
=T(n-2)+T(n-3)+2+T(n-3)+T(n-4)+2
etc

Hope this helps.
yeah I understand the theory. but it will continue until no end. I am having trouble to simplified it. so I really need to know how to simplified it
Look at the pattern for each time you unravel the recurrence equation. How many term are there each time? Can you think of a mathematical operation that models that? (Hint, ignore constant terms.)
Topic archived. No new replies allowed.