CODEWITHSUNDEEP
algorithmfibonacci
noviceneedshelp
noviceneedshelp

Reputation: 177

Solving Recursion in fibonacci numbers

I'm unaware of the mathematics in this algorithm and could use some help.

Algorithm:

if n<2 then

  return n

else return fibonacci(n-1) + fibonacci(n-2)

Statement

n < 2 is O(1)
Time n >=2 is O(1)
Return n is O(1) Time n>=2 is - Return fib(n-1) + fib(n-2) is -

and time n>=2 is T(n-1) + T(n-2) +O(1)

Total: O(1) T(n-1) + T(n-2) + O(1)
T(n) = O(1) if n < 2
T(n) = T(n-1) + T(n-2) + O(1) if n>=2

Upvotes: 3

Views: 1533

Answers (3)

Craig Gidney
Craig Gidney

Reputation: 18276

I think you're supposed to notice that the recurrence relation for this function is awfully familiar. You can learn exactly how fast this awfully familiar recurrence grows by looking it up by name.

However, if you fail to make the intuitive leap, you can try to bound the runtime using a simplified problem. Essentially, you modify the algorithm in ways guaranteed to increase the runtime while making it simpler. Then you figure out the runtime of the new algorithm, which gives you an upper bound.

For example, this algorithm must take longer and is simpler to analyze:

F(n): if n<2 then return n else return F(n-1) + F(n-1)

Upvotes: 4

Vlad
Vlad

Reputation: 35584

By induction: if calculation of fib(k) takes less than C*2^k for all k < n, for the calculation tome of fib(n) we've got

T(n) = T(n-1) + T(n-2) + K < C*2^(n-1) + С*2^(n-2) + K
     = 0.75*C*2^n + K < C*2^n

for sufficiently big C (for C > K/0.25, as 2^n > 1). This proves that T(n) < C*2^n, i.e. T(n) = O(2^n).

(Here T(n) is the time for calculation of fib(n), K is the constant time needed for calculating fib(n) when both fib(n-1) and fib(b-1) are [already] calculated.)

Upvotes: 3

Ismael
Ismael

Reputation: 344

You need to solve the recurrence equation:

T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2), for all n > 1

Upvotes: 0

Related Questions