CODEWITHSUNDEEP
algorithmequationrecurrence
Mohd Alomar
Mohd Alomar

Reputation: 980

recurrence equation from fibonacci algorithm

I want to find the recurrence equation to compute the time complexity 

    int Fib(int n)
{
    if (n <= 1)
        return n;
    else
        return Fib(n - 1) + Fib(n - 2);
}

I can solve the recurrence equation, but I have difficulty to find the equation and the base case.

Is this the correct equation ?

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

and for the base case ?

T(0)=0

T(1)=0

Also in general how the base case for an algorithm can found ?

Upvotes: 3

Views: 1690

Answers (1)

Steve Jessop
Steve Jessop

Reputation: 279255

For complexity, the base case in this example doesn't usually matter. Personally I'd probably set T(0) = 1, T(1) = 1, on the basis that nothing takes zero time. But just look at your recurrence relation. It is itself a Fibonacci-style sequence, it's going to be exponential (almost-) regardless of the base cases.

The general problem for base cases is that you want a concrete answer ("how long does it take to compute Fib(0)?"), but the actual "units of time" in complexity calculations are usually poorly defined. To be precise, you should define T(0) equal to a constant k_1, and T(1) equal to a constant k_2, and work from there. If you need numeric values for the constants in order to solve the recurrence relation, then something has probably gone wrong.

Similarly, you could set your recurrence relation to T(n) = T(n-1) + T(n-2) + k_3.

Note that if the "unit of time" for your complexity calculation is "number of executions of addition", ignoring the other logic, then your base cases are correct at 0. This would be a useful way to analyse the time if (for example) the addition were done by a user-supplied function whose performance is outside the scope of your analysis.

Upvotes: 3

Related Questions