6 ms·
None of this is true. >fibonacci growth is strictly faster than exponential There is even an explicit formula for F(n) that shows fibonacci growth is exactly
by ithinkso 12y ago
None of this is true.
>fibonacci growth is strictly faster than exponential
There is even an explicit formula for F(n) that shows fibonacci growth is exactly exponential[1]
>In fact, this is why nlog(n) is the lower bound on the number of comparisons a comparison-based sorting algorithm
It's true that lower bound for comparison-based sorting is nlog(n) but it has nothing to do with fibonacci
>n! is approximately nlog(n)
Stirling's formula[2] says otherwise (that n! is exponential)
[1] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
[2] http://en.wikipedia.org/wiki/Stirling%27s_approximation http://en.wikipedia.org/wiki/Stirling%27s_approximation
- noahl 12y agoHow embarrassing! It looks like I flipped around Fibonacci and factorial in my head when writing my reply. You're completely right that the comparison-based sorting bound has nothing to do with Fibonacci numbers. And in fact log_2(n!) is about n*log_2(n), which is where the comparison-based sorting bound comes from. And Fibonacci growth is absolutely exponential, just with an exponent larger than 2.