On Tue, May 1, 2012 at 12:00 PM, Dan Stromberg <drsali...@gmail.com> wrote: > > On Tue, May 1, 2012 at 12:21 AM, Ian Kelly <ian.g.ke...@gmail.com> wrote: >> >> On Mon, Apr 30, 2012 at 11:25 PM, Dan Stromberg <drsali...@gmail.com> >> wrote: >> > >> > A while back I did a sort algorithm runtime comparison for a variety of >> > sorting algorithms, and then mostly sat on it. >> > >> > Recently, I got into a discussion with someone on stackoverflow about >> > the >> > running time of radix sort. >> > >> > I realize it's commonly said that radixsort is n*k rather than n*log(n). >> > I've been making that case that in real life, frequently k==log(n). >> > >> > Anyway, here's the comparison, with code and graph: >> > http://stromberg.dnsalias.org/~strombrg/sort-comparison/ >> >> It can be difficult to distinguish O(n) from O(n log n) on a log-log >> plot, so I don't think that graph makes your point very well. > > Thank you for your comment. > > Do you have a suggestion for a better type of graph - or other > linearity/nonlinearity test?
An ordinary linear-scale graph. It will only show the highest order of magnitude in any detail, but for determining asymptotic behavior that's the most interesting part anyway. O(n) should look like a straight line, and O(n log n) should curve up with a gradually increasing slope. Alternatively, calculate regressions and compare the goodness of fit. > I thought that on a log-log graph, a straight line was still a straight > line, but it's compressed at one end. The key characteristic of a log-log plot is that any curve y = ax ** b will appear as a straight line with a slope of b. So a linear curve will be a straight line with a slope of 1. A O(n log n) curve will converge to a straight line with a slope of 1 as n approaches infinity. -- http://mail.python.org/mailman/listinfo/python-list
