When you say 'm is a small constant' you are again making a totally inappropriate assumption about limiting the key field size. When you make that assumption you're no longer allowed to use the O() operator because it is solely defined in the asymptotic case where all relevant variables are increased towards infinity, including m.
Perhaps I wasn't very clear with my intended definition of m. If the key field is 16 bits, then M is 2^16, not 16.
Anyway, switching to your intended definition of m, O(m) still must equal or exceed O(ln(n)) in order to have a unique sorting order. The execution time is O(m * n), which still equals or exceeds O(ln(n)*n) no matter how you slice it.
However, there are sorts that work in O(n) time, not O(n log(n)) such as a radix sort which does not use the comparison operator (a/k/a "if-then-else").
Bullcrap. Radix sort works in O(ln(m) * n) time where n is the number of elements and m is the
size of the key field. Since m has to be greater than or equal to n to have a unique sorting order, O(ln(m)*n) is greater than O(ln(n)*n).
If you make the idiotic assumption that the key field is of a fixed size, then you are no longer permitted to use the big-O operator. big-O is only defined in the asymptotic case, where you take the limit as all relevant variables are increased to infinity. You might as well say that bubble sort is O(1) in the case where n is smaller than 100.
So what happens when everybody starts carrying these things onto planes? Will the airlines charge extra for the additional oxygen consumed? How much oxygen does one of these things use compared to a typical person?
Slashdot Mirror
Perhaps I wasn't very clear with my intended definition of m. If the key field is 16 bits, then M is 2^16, not 16.
Anyway, switching to your intended definition of m, O(m) still must equal or exceed O(ln(n)) in order to have a unique sorting order. The execution time is O(m * n), which still equals or exceeds O(ln(n)*n) no matter how you slice it.
Bullcrap. Radix sort works in O(ln(m) * n) time where n is the number of elements and m is the size of the key field. Since m has to be greater than or equal to n to have a unique sorting order, O(ln(m)*n) is greater than O(ln(n)*n).
If you make the idiotic assumption that the key field is of a fixed size, then you are no longer permitted to use the big-O operator. big-O is only defined in the asymptotic case, where you take the limit as all relevant variables are increased to infinity. You might as well say that bubble sort is O(1) in the case where n is smaller than 100.
So what happens when everybody starts carrying these things onto planes? Will the airlines charge extra for the additional oxygen consumed? How much oxygen does one of these things use compared to a typical person?