Hacker News Reader

Comment by EpicDavi | Hacker News Reader

Just a semi-unrelated comment:

The Fibonacci code example classically has a horrid runtime. Will like likely crash your browser when supplied a number higher than the low thirties. IIRC it has a O(2^n) runtime and can be improved either by a bottom up approach (non-recursive) or a "dynamic-programming" (OOohhhh, buzzwords) method where you use memoization (memo table) to store (or memoize) results.

View on HN

I always thought the fastest was the closed form formula: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

Unless looping and counting is that much faster than doing some floating point math?

Only "faster" because you precompute digits of the golden ratio, and will quickly become inaccurate unless you compute more of them

The closed form will become inaccurate at some point. However, there is a way to calculate Fibonacci accurately with O(log(n)) time (ignoring the time to multiply - otherwise O(M(n) log(n)) where M(n) is the time to multiply two numbers of n digits).

I thought recursive fibonacci solutions like this had O(fib n) run time.

You're both correct: http://stackoverflow.com/questions/4623058/ofib-n-complexity...

EDIT: Tied with JadeNB (https://news.ycombinator.com/item?id=8555051).

but isn't O(phi^n) < O(2^n)? Exponential regardless.

Sure, O(2^n) is an upper bound here. O(phi^n) is a tighter bound.

You're right, although the "<" symbol isn't technically correct notation. I think O(phi^n) ⊂ O(2^n) or O(phi^n) ⊊ O(2^n) would be more correct to indicate that the left is a proper subset of the right, given that big O notation refers to sets of functions.

That's certainly true, although notation like `fib_n = O(phi^n)` (rather than `fib_n \in O(phi^n)`) is so ingrained that it's probably too late to fight it. (I seem to remember that Knuth says something to this effect.)

In that spirit, one can adopt a sort of compromise notation: `O(phi^n) = o(2^n)` (where `=` should really be `\subseteq`).

> EDIT: Tied with JadeNB (https://news.ycombinator.com/item?id=8555051).

So close, and only ngorenflo (https://news.ycombinator.com/item?id=8555050) can come between us. :-)

`O(fib_n)` is `O(phi^n)`, where phi = (1 + sqrt(5))/2 < 2.

EDIT: Tied with Mithrandir (https://news.ycombinator.com/item?id=8555049).

Reply on news.ycombinator.com