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

Question

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 𝜃(φⁿ). 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.

molbdnilo · Accepted Answer · 2020-05-18 12:56:33Z

1

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 𝜃(φⁿ).

answered May 18, 2020 at 12:56

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

President James K. Polk Over a year ago

where φ = (1 + sqrt(5)) / 2? But that is the approximate size of the fib(n), not the complexity of computing it.

Sylwester Over a year ago

@PresidentJamesK.Polk If you take f(10) and use the substitution model you'll end up with a line adding 1's together f(10) times. Thus the complexity of fib(n) is O(fib(n))

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related