<br><div class="gmail_quote">On Tue, May 1, 2012 at 11:52 AM, Ian Kelly <span dir="ltr"><<a href="mailto:ian.g.kelly@gmail.com" target="_blank">ian.g.kelly@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On Tue, May 1, 2012 at 12:00 PM, Dan Stromberg <<a href="mailto:drsalists@gmail.com">drsalists@gmail.com</a>> wrote:<br>
><br>
> On Tue, May 1, 2012 at 12:21 AM, Ian Kelly <<a href="mailto:ian.g.kelly@gmail.com">ian.g.kelly@gmail.com</a>> wrote:<br>
>><br>
>> On Mon, Apr 30, 2012 at 11:25 PM, Dan Stromberg <<a href="mailto:drsalists@gmail.com">drsalists@gmail.com</a>><br>
>> wrote:<br>
>> ><br>
>> > A while back I did a sort algorithm runtime comparison for a variety of<br>
>> > sorting algorithms, and then mostly sat on it.<br>
>> ><br>
>> > Recently, I got into a discussion with someone on stackoverflow about<br>
>> > the<br>
>> > running time of radix sort.<br>
>> ><br>
>> > I realize it's commonly said that radixsort is n*k rather than n*log(n).<br>
>> > I've been making that case that in real life, frequently k==log(n).<br>
>> ><br>
>> > Anyway, here's the comparison, with code and graph:<br>
>> > <a href="http://stromberg.dnsalias.org/%7Estrombrg/sort-comparison/" target="_blank">http://stromberg.dnsalias.org/~strombrg/sort-comparison/</a><br>
>><br>
>> It can be difficult to distinguish O(n) from O(n log n) on a log-log<br>
>> plot, so I don't think that graph makes your point very well.<br>
><br>
> Thank you for your comment.<br>
><br>
> Do you have a suggestion for a better type of graph - or other<br>
> linearity/nonlinearity test?<br>
<br>
</div>An ordinary linear-scale graph.  It will only show the highest order<br>
of magnitude in any detail, but for determining asymptotic behavior<br>
that's the most interesting part anyway.  O(n) should look like a<br>
straight line, and O(n log n) should curve up with a gradually<br>
increasing slope.  Alternatively, calculate regressions and compare<br>
the goodness of fit.<br>
<div class="im"><br>
> I thought that on a log-log graph, a straight line was still a straight<br>
> line, but it's compressed at one end.<br>
<br>
</div>The key characteristic of a log-log plot is that any curve y = ax ** b<br>
will appear as a straight line with a slope of b.  So a linear curve<br>
will be a straight line with a slope of 1.  A O(n log n) curve will<br>
converge to a straight line with a slope of 1 as n approaches<br>
infinity.<span class="HOEnZb"><font color="#888888"><br></font></span></blockquote><div><br>Thanks for the info.<br><br>I actually feel like both the log-log graph and the linear-linear graph, tell an interesting but different part of the story, so I've kept the log-log graph and added a linear-linear graph.<br>
<br>I also added a linear-line to the linear-linear graph, for the sake of comparison.<br><br>You can see that radix sort is falling between mergesort and quicksort (both nlogn on average), and radix sort is coming up almost parallel to mergesort.<br>
 <br></div></div><br>