4 ms·
It’s fun how the runtime in seconds for the naive Fibonacci is 36: 14930352 (1.2s) 37: 24157817 (2.0s) 38: 39088169 (3.2s) 39: 63245986 (5.2s) 40: 10
by User23 2y ago
It’s fun how the runtime in seconds for the naive Fibonacci is
36: 14930352 (1.2s)
37: 24157817 (2.0s)
38: 39088169 (3.2s)
39: 63245986 (5.2s)
40: 102334155 (8.3s)
41: 165580141 (13.5s)
42: 267914296 (21.8s)
What a familiar pattern in those runtimes!
- izietto 2y agoFibonacci never stops surprising!
- JadeNB 2y agoThat'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).
- thih9 2y agoI know it’s pointless but now I’d like to see a fibonacci implementation that returns these runtimes as the result.
- kazinator 2y agoAnother kind of fun with Fibonacci (sort of): https://news.ycombinator.com/item?id=14331627 https://news.ycombinator.com/item?id=14331627 floor(x + 0.5) wants to be round(x), that function having been introduced in C99. Just remnants of old school C coding.