checking running time of recursive alg

[Mindcraft]

is there a way i can analytically calculate the running time of a recursive algorithm? for instance, lets say i have the fib sequence defined recursively as follows:

int f(int n)
{
if (n == 0 or n == 1)
return n;
else
return f(n-1) + f(n-2);
}

how can i find out the running time of this example, and recursive examples in general?

thanks

[the tree]

This is incredibly simple.

Strait before running the function set a variable equal to the current time, for auguments sake call it starttime, strait after running the function set another variable equal to the current time and all it endtime.

endtime - starttime = runtime.

[Mindcraft]

Originally posted by the tree
This is incredibly simple.

Strait before running the function set a variable equal to the current time, for auguments sake call it starttime, strait after running the function set another variable equal to the current time and all it endtime.

endtime - starttime = runtime.

Sure, this works. But, don't you think this method is completely empirical? I'd like to know if there is a strictly analytical method to compute the running time. Thanks

[AdamGundry]

If you are talking about the theoretical running time of an algorithm, rather than a practical instance, things get a bit more complicated mathematically. Essentially, the running time of such an algorithm is a recurrence relation (also known as a recurrence equation) which can be solved to give bounds for the time.

The simple recursive algorithm for the Fibonacci sequence is exponential in the size of the input number, but there are faster algorithms. This can be shown thus:

Let f(n) be the running time of the algorithm for input n, and let t1 and t2 be some constants.
For n=0 and n=1, f(n) = t1
For n>=2, f(n) = t2 + f(n-1) + f(n-2)
f(n) > 2f(n-2)
f(n) > t1 * 2^(n/2)

Hence this algorithm runs in exponential time.

Adam