5 ms·

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 t

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.

dopamean 12y ago
I thought recursive fibonacci solutions like this had O(fib n) run time.
- 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 ago
    but isn't O(phi^n) < O(2^n)? Exponential regardless.
    - Mithrandir 12y ago
      Sure, O(2^n) is an upper bound here. O(phi^n) is a tighter bound.
    - baddox 12y ago
      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.
      - JadeNB 12y ago
        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`).
  - 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. :-)
- JadeNB 12y ago
  `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 https://news.ycombinator.com/item?id=8555049).
MrRage 12y ago
I always thought the fastest was the closed form formula: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex... Unless looping and counting is that much faster than doing some floating point math?
- aarongolliver 12y ago
  Only "faster" because you precompute digits of the golden ratio, and will quickly become inaccurate unless you compute more of them
- Bognar 12y ago
  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).

dopamean 12y ago

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

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 ago
  but isn't O(phi^n) < O(2^n)? Exponential regardless.
  - Mithrandir 12y ago
    Sure, O(2^n) is an upper bound here. O(phi^n) is a tighter bound.
  - baddox 12y ago
    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.
    - JadeNB 12y ago
      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`).
- 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. :-)
JadeNB 12y ago
`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 https://news.ycombinator.com/item?id=8555049).

MrRage 12y ago

I always thought the fastest was the closed form formula: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex... Unless looping and counting is that much faster than doing some floating point math?

aarongolliver 12y ago
Only "faster" because you precompute digits of the golden ratio, and will quickly become inaccurate unless you compute more of them
Bognar 12y ago
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).