Algorithm cost for recursive funtion

[rrvv]

so I have some problem to determined algorithm cost of this program

  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.

[pheininger]

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().

[Duthomhas]

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.

[rrvv]

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

[Duthomhas]

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.)