Complexity of Sorting Algorithms Sort a number of n integers. The value of the integers ranges from 0 to n4-1. Please provide the worst-case running time for the following sorting algorithms (1) ~(5) using big-O or big-Θ notation wherever appropriate. (1) Insertion Sort: (2) Merge Sort: (3) Quick Sort: (4) Counting Sort: (5) Radix Sort:
Complexity of Sorting
Sort a number of n integers. The value of the integers ranges from 0 to n4-1. Please provide the worst-case running time for the following sorting algorithms
(1) ~(5) using big-O or big-Θ notation wherever appropriate.
(1) Insertion Sort:
(2) Merge Sort:
(3) Quick Sort:
(4) Counting Sort:
(5) Radix Sort:
1. Insertion Sort:
Worst case time complexity of insertion Sort is O(n^2), this can be possible when the array is reverse order when there is
n*(n-1)/2 inversion occurs . In best case time complexity is O(N) and in avg case time complexity is O(N^2).
The worst case time complexity is O(N^2)
2. Merge Sort :
Time complexity of Merge Sort is O(n*Log n) in worst case , avg case and best case also. In merge sort the whole array is divided into 2 sub-array and calling the merge sort on these subarray as well as merge these two halves.
T(n)= 2T(n/2)+O(n) solving these recurrence will give T(n)=O(NlogN)
The worst case time complexity is O(NlogN)
3. Quick Sort :
The worst case time complexity QuickSort is O(n2).
The worst case situation occurs when the input array is sorted or reverse given or last or first element is pivot.
The worst-case situation occurs when the picked pivot is always an smallest or largest element .
The worst case time complexity is O(N^2).
4. Counting Sort :.
Counting sort basically works with counting the number of objects having distinct key values
Counting sort uses O(N+K) time in worst case
5. Radix Sort :
This sorting algorithm uses counting sort as a subroutine to sort an array of numbers .
Radix sort uses O(N*K) time in the worst case .
Step by step
Solved in 2 steps
