> first, counting sort takes O(n * R) O(n + R), actually: http://en.wikipedia.org/wiki/Counting_sort#Analysis http://en.wikipedia.org/wiki/Counting_sort#Analys

> first, counting sort takes O(n * R) O(n + R), actually: http://en.wikipedia.org/wiki/Counting_sort#Analysis http://en.wikipedia.org/wiki/Counting_sort#Analysis I agree that he overstates radix sort though. Asymptotically it just changes the runtime from O(n log n) (ala quicksort) to O(n log k) where k is the size of the set of possible numbers, and usually n is smaller than k. Dividing into 256 parts instead of 2 at each step changes the constant, but not the asymptotic big O. You could do the same with quicksort (at each step choose 255 random pivots and use them to define 256 buckets of sublists). That changes the average runtime from n log_2 n to n log_256 n, but the only difference is a constant factor.