3 ms·
That's a neat observation! But isn't it for the naïve reason that, with negligible overhead, the run time of executing `fib(n) = fib(n - 1) + fib(n - 2)` is th
by JadeNB 2y ago
That's a neat observation! But isn't it for the naïve reason that, with negligible overhead, the run time of executing `fib(n) = fib(n - 1) + fib(n - 2)` is the run time of executing `fib(n - 1)`, plus the run time of executing `fib(n - 2)`?
On the other hand, if someone had asked me for an estimate on the run time, I probably would have tried breaking out the master theorem instead of thinking of this, so I don't want to downplay the observation.
- bmm6o 2y agoRight. Also note that the non-optimized implementation boils down to computing F(n) = 1+1+1+1+...+1, with a function call tree that has 2F(n) nodes. So no matter what the relative cost is for addition and function calls, the total time should go like F(n).