4 ms·
The real reason why it's such a poor example is that it's contrived. If you honestly wanted to determine arbitrary elements from the Fibonacci series you would
by InclinedPlane 17y ago
The real reason why it's such a poor example is that it's contrived. If you honestly wanted to determine arbitrary elements from the Fibonacci series you would calculate them using a closed form expression that runs in O(1) (wiki Fibonacci sequence for examples).
Similarly, factorial is often a poor example problem because it's almost always completely unnecessary to tweak the performance of any algorithm for real world inputs. 13! is larger than an unsigned 32-bit int can hold, and 21! is larger than an unsigned 64-bit int can hold. The amount of performance gain you'd get from shaving down a loop or recursive call that ran at most 20 times is inconsequential in the vast majority of cases. Indeed, a simple recursive or iterative method is probably more efficient than even a lookup table method in most cases.
As example problems to see how people think through issues of iteration vs. recursion, efficiency, and performance these are ok problems but as real-world benchmarks for any kind of coding style they are terribly artificial.
- klodolph 17y agoThe closed form solution isn't O(1). It's Ω(2^N) since the number of digits in the output is Θ(2^N).
- InclinedPlane 17y agoOn the most prevalent electronic computers of our time the closed form solution is effectively constant-time if the output is bounded to be within the limits of a 32 or 64 bit integer.