In: Computer Science
Please PROVE the following statement: The time complexity of any sorting algorithm that uses only comparisons between elements is the following:
Ωn log n in the worst case. you need to prove this , if you can please type answer.
Analysis of different sorting technique
Time complexity Analysis –
We have discussed the best, average and worst case complexity of
different sorting techniques with possible scenarios.
Comparison based sorting –
In comparison based sorting, elements of an array are compared with
each other to find the sorted array.
T(n) = T(k) + T(n-k-1) + cn
Worst case: when the array is sorted or reverse sorted, the partition algorithm divides the array in two subarrays with 0 and n-1 elements
Non-comparison based sorting –
In non-comparison based sorting, elements of array are not compared
with each other to find the sorted array.
Time and Space Complexity Comparison Table :
Sorting Algorithm | Time Complexity | Space Complexity | ||
---|---|---|---|---|
Best Case | Average Case | Worst Case | Worst Case | |
Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
Selection Sort | Ω(N2) | Θ(N2) | O(N2) | O(1) |
Insertion Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
Quick Sort | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
Radix Sort | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) |
O(N) |