Choosing between 2 Fibonacci alternatives
You can compute fibonacci numbers with both time and space complexity O(1).

(n) =&gt; ((Math.Pow(phi,n) - Math.Pow(1-phi, n)) / Math.Sqrt(5);


where phi is the golden ratio:

(1 + Math.Sqrt(5)) / 2


But if you needed to iterate fibonacci numbers one after the other, I would use an "iterator", then every other number would also be generated in O(1) and it would be better then the double formula.