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? I thought that on a log-log graph, a straight line was still a straight line, but it's compressed at one end.
-- http://mail.python.org/mailman/listinfo/python-list
