Hacker News Reader

Comment by User23 | Hacker News Reader

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!

View on HN

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.

Right. 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).

I know it’s pointless but now I’d like to see a fibonacci implementation that returns these runtimes as the result.

Another kind of fun with Fibonacci (sort of):

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.

Fibonacci never stops surprising!

Reply on news.ycombinator.com