Radix Sort Time Complexity

Introduction: The radix sort is a different type of sorting algorithm than others and is used by most people to sort a large list of names alphabetically. 'Radix' word can be defined as 'base' in the section of number conversion(like as decimal to binary or binary to octal decimal). Radix is different in the different representations of sorting. The list is given below, 

Radix = 2 = for the bits

Radix = 10 = for the decimal digits

Radix = 26 = for the letters

The radix

Fig. 01: The radix

Radix Sort Time Complexity

Assume that an array data list 'a' of n items or n-length is given. The data array has (a1, a2, a3, ....., an) elements. Again assume that each item of the array 'a' can be represented by the 'p'. The 'p' is the passes needed to change the index number of the array elements. 

The data array 'a'

Fig. 02: The data array 'a'

The radix sort depends on the three parameters. Parameters are,

r = r denote the radix or base of a number

p = p denote the passes needed for sorting elements

n = n denote the items in the array


The radix sort process will be required p passes for the number of numerals. Each of the passes will compare with n elements in the data array. Then, the number of comparisons for the n-length array is bounded by the following,

Radix(n) = r * p * n

Generally, the radix 'r' is independent of the n numbers but the 'p' passes depending on the n numbers.  For the worst case, pass = numbers, then the time complexity can be written below, 

worst case Radix(n) = O (1) * O(n) * O(n)

    =O (n2)

For the best case, pass = logr n, then time complexity of radix sort will be,

Best case Radix(n) = O(1) * O(logr n) * O(n)

   =O (n logr n)

In other words, the radix sort performs better when the number of n digits with p passes of the data array 'a' is small.

 The drawback of the radix sort in the space complexity is that it needs r*n memory locations. But this drawback can be minimized using the linked list algorithm. However, the reality is, this sorting algorithm still needs two times of n-length memory location.

The space complexity of the radix sort is will be the same as the time complexity and that is O (n2)

Read Similar Post

1. Merge Sort Time Complexity

2. Quick Sort Time Complexity

3. Insertion Sort Time Complexity

4. Runtime Reduction of a Linear Search

5. Selection Sort Time Complexity

6. Bubble Sort Time Complexity

7. Heap Sort Time Complexity

8. Binary Search Tree Time Complexity

Post a Comment

Previous Post Next Post