In Radix Sort,
Time Complexity : O(nd)
Space Complexity: O(n+RADIX)
However, by changing RADIX, one can reduce d and get as low as O(n) which is similar to counting sort which uses the RADIX size equal to the range of array (Normalization or pull up is required if there are some negative numbers).
But that will cause rise in Space Complexity that is directly proportional to RADIX.
Careful selection of RADIX for a particular problem will help in sorting close to linear time and less space.
Please feel free to comment if you feel any error in it.
Posts
No comments:
Post a Comment