4 ms·
No, in the merge sort example it's not 32n operations, but a maximum of 32 levels of splits, but the number of comparisons, which dominate runtime, is still k *
by pmjordan 17y ago
No, in the merge sort example it's not 32n operations, but a maximum of 32 levels of splits, but the number of comparisons, which dominate runtime, is still k * n * log(n). Not so for radix sort, because there are no direct comparisons. By choosing a word length in advance (often hard-coded) the number of items to sort affects the runtime linearly.
- Yrlec 17y agoI think you are mixing runtime scalability with the actual complexity. Big-O definition from Wikipedia: Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes f(x) = O(g(x)) as x -> infinity if and only if, for sufficiently large values of x, f(x) is at most a constant times g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that |f(x)| <= M|g(x)| for all x > x0. In the above case M = 32, f = mergesort and g(x) = x because no matter of large input you have mergesort will always take less than or equal to 32n operations (since log(n)<=32) .