Hacker News Reader

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

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

Reply on news.ycombinator.com