Hacker News Reader

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