Question

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.

Answer 1

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.

• Bubble sort and Insertion sort –
  Average and worst case time complexity: n^2
  Best case time complexity: n when array is already sorted.
  Worst case: when the array is reverse sorted.
• Selection sort –
  Best, average and worst case time complexity: n^2 which is independent of distribution of data.
• Merge sort –
  Best, average and worst case time complexity: nlogn which is independent of distribution of data.
• Heap sort –
  Best, average and worst case time complexity: nlogn which is independent of distribution of data.
• Quick sort –
  It is a divide and conquer approach with recurrence relation:

   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.

• Radix sort –
  Best, average and worst case time complexity: nk where k is the maximum number of digits in elements of array.
• Count sort –
  Best, average and worst case time complexity: n+k where k is the size of count array.
• Bucket sort –
  Best and average time complexity: n+k where k is the number of buckets.
  Worst case time complexity: n^2 if all elements belong to same bucket.

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)