4 ms·
Just a nitpick, but the article makes a mathematical mistake. In the last paragraph of section 1.2, it says For performance reasons, it is crucial to alloc
by noahl 12y ago
Just a nitpick, but the article makes a mathematical mistake. In the last paragraph of section 1.2, it says
For performance reasons, it is crucial to allocate as
little memory as possible for runLen, but still enough to
store all the runs. *If the invariant is satisfied by all
runs, the length of each run grows exponentially (even faster
than fibonacci: the length of the current run must be
strictly bigger than the sum of the next two runs lengths).*
However, fibonacci growth is strictly faster than exponential. In fact, this is why n * log(n) is the lower bound on the number of comparisons a comparison-based sorting algorithm must use: because n! is approximately n * log(n).
- robrenaud 12y ago> fibonacci growth is strictly faster than exponential. This is wrong. The easiest intuition for why this is true that I can come up with is that next Fibonacci number is no bigger than double the previous, and so fib(n) <= 2^n.
- anonymoushn 12y agoFibonacci is n(i) = n(i-1) + n(i-2). Factorial is n! = n * n-1 * n-2 * ... * 2 * 1. In the second sentence, you might have wanted "lg(n!) is approximately n lg n". That would be a good reason for needing n lg n comparisons to distinguish between the n! permutations. I have edited this comment as my understanding of the parent comment developed >_>
- noahl 12y agoThanks for pointing this out! Yes, I meant log_2(n!) is approximately n*log_2(n). I appreciate you spotting the error. :-)
- deleted 12y ago[deleted]
- bladedtoys 12y agoFibonacci( n ) = ( P^n - ( -P )^-n ) / sqrt(5) Where P is Golden ratio ( about 1.618 ) So yes it resembles exponential growth but as you can see it is slightly less due to the "- ( -P )^-n" part.
- ithinkso 12y agoNone 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.