5 ms·
You're both correct: http://stackoverflow.com/questions/4623058/ofib-n-complexity-algorithms/4623285#4623285 http://stackoverflow.com/questions/4623058/ofib-n-c
by Mithrandir 12y ago
You're both correct: http://stackoverflow.com/questions/4623058/ofib-n-complexity-algorithms/4623285#4623285 http://stackoverflow.com/questions/4623058/ofib-n-complexity...
EDIT: Tied with JadeNB (https://news.ycombinator.com/item?id=8555051 https://news.ycombinator.com/item?id=8555051).
- lqdc13 12y agobut isn't O(phi^n) < O(2^n)? Exponential regardless.
- Mithrandir 12y agoSure, O(2^n) is an upper bound here. O(phi^n) is a tighter bound.
- baddox 12y agoYou'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.
- JadeNB 12y agoThat'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`).
- JadeNB 12y ago> EDIT: Tied with JadeNB (https://news.ycombinator.com/item?id=8555051 https://news.ycombinator.com/item?id=8555051). So close, and only ngorenflo (https://news.ycombinator.com/item?id=8555050 https://news.ycombinator.com/item?id=8555050) can come between us. :-)