Algorithm Design Questions Medium
The time complexity of the counting sort algorithm is O(n + k), where n is the number of elements to be sorted and k is the range of the input values.
Counting sort is a non-comparative sorting algorithm that works by determining the number of occurrences of each distinct element in the input array and using this information to determine the correct position of each element in the sorted output array. It is efficient when the range of input values is small compared to the number of elements to be sorted.
The algorithm first creates a count array of size k, where k is the maximum value in the input array. It then iterates through the input array, incrementing the count of each element in the count array. Next, it modifies the count array by adding the previous count to the current count, which gives the position of each element in the sorted output array. Finally, it iterates through the input array again and places each element in its correct position in the output array based on the count array.
The time complexity of counting sort is dominated by the two iterations through the input array. Therefore, the time complexity is linear, O(n), where n is the number of elements in the input array. Additionally, the time complexity is also dependent on the range of input values, as the count array needs to be created and modified accordingly. Hence, the time complexity is O(n + k).