CODEWITHSUNDEEP
algorithmmathschemetime-complexityfibonacci
user168651
user168651

Reputation: 55

SICP: I'm having trouble understanding the time complexity of the Fibonacci algorithim

I'm reading through SICP. It's my first introduction to computer science.

The book presents the Fibonacci algorithm below:

(define (fib n)
  (cond 
    ((= n 0) 0)
    ((= n 1) 1)
    (else (+ (fib (- n 1)) 
             (fib (- n 2))))))

The book mentions that the space this algorithm takes up is 𝜃(n) and the time it takes is 𝜃(φn). I understand the space complexity since it is the max depth of a tree, but I can't seem to wrap my head around how the time complexity is derived.

Upvotes: 0

Views: 211

Answers (1)

molbdnilo
molbdnilo

Reputation: 66441

If you write down how much time it takes in each case (1 is constant),

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

you see that it is exactly the same as the Fibonacci numbers.
And as the text (almost) says, Fib(n) is 𝜃(φn).

Upvotes: 1

Related Questions