Radix Sort
For a general definition of time complexity, see this page.
Radix Sort Time Complexity
The Radix Sort algorithm sorts non negative integers, one digit at a time.
There are n values that need to be sorted, and k is the number of digits in the highest value.
When Radix Sort runs, every value is moved to the radix array, and then every value is moved back into the initial array. So n values are moved into the radix array, and n values are moved back. This gives us n+n=2⋅noperations.
And the moving of values as described above needs to be done for every digit. This gives us a total of 2⋅n⋅k operations.
This provides us with Radix Sort’s time complexity:
===formula===
As long as the number of digits (k) is maintained reasonably small in relation to the number of values, the Radix Sort sorting algorithm may be the fastest available. n..
We can imagine a scenario where the number of digits kis the same as the number of values n, in such a case we get time complexity O(n⋅k)=O(n2) which is quite slow, and has the same time complexity as for example Bubble Sort.We can also image a scenario where the number of digits k grow as the number of values n grow, so that k(n)=logn.
In such a scenario we get tie complexity O(n⋅k)=O(n⋅logn), which is the same as for example Quicksort.
View the following graphic to see the Radix Sort time complexity.
Radix Sort Simulation
Run different simulations of Radix Sort to see how the number of operations falls between the worst case scenario O(n2) (red line) and best case scenario O(n)(green line).
===image===
To make it look okay, the bars that indicate the various numbers are scaled to fit the window. This implies that although values with seven digits appear to be only five times larger than values with two digits, in actuality, values with seven digits are five thousand times larger!
If we are holding n additionally k Thus, the number of operations is the same for the “Random,” “Descending,” and “Ascending” possibilities in the scenario above. This is so because all three scenarios have the same outcome.
