News for hackers. Stuff that matters.
Re:Big-O Algorithm Complexity Cheat Sheet by jules on Saturday May 04, 2013 @06:55PM (#5656627)
Quicksort is O(k*n log n) though since it does O(n log n) comparisons and a comparison is going to be O(k), so radix sort is still asymptotically faster.
Re:Big-O Algorithm Complexity Cheat Sheet by nostrademons on Saturday May 04, 2013 @09:19PM (#5657042)
See response to Retric:

https://news.ycombinator.com/item?id=5656534

A comparison isn't always O(k). It's O(k) for strings. It's O(1) for machine-word integers. It can be much more than O(k) for user-defined types, eg. it can be O(k^3) if you have to multiply a matrix out and take the determinant of the product.

Re:Big-O Algorithm Complexity Cheat Sheet by jules on Sunday May 05, 2013 @12:44PM (#5658913)
For word sized integers, k=O(1) so radix sort is O(n) and quicksort is O(n log n). If you have a comparison function that takes O(k^3) then you most likely can't even implement a radix sort for it, so the comparison can't be made.

So the fact is that quicksort is a factor O(log n) slower than radix sort. The flip side is that quicksort is more generally applicable to any comparison function whereas radix sort only works for lexicographic sorts. In almost all cases that is exactly what you want, but for example I'm not aware of any way to efficiently sort rational numbers with radix sort.