How explosive is naive Fibonacci?
The naive doubly-recursive fib (with fib(0)=0, fib(1)=1) recomputes everything. Counting the top call and every recursive call, how many calls does it take to evaluate fib(6)?
Show hints (2)+
- Each call to
fib(n)makes two child calls; count nodes in the call tree. - , with .
Answer
Reveal answer →Final answer
25
Create a free account to see the full worked solution and track your progress.
Interview format: Hedge Fund Quant, Systematic & Data-Driven Trading