Array Sorting Algorithms Complexicity Big Oh Chart

Last time Preparation notes of Sorting algorithm for Gate CSE.

Algorithm Time Complexity Space Complexity
Best Average Worst Worst
Quick sort Ω(n log(n)) Θ(n log(n)) O(n2) O(log(n))
Merge sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Tim sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)
Heap sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Bubble Sort Ω(n) Θ(n2) O(n2) O(1)
Insertion Sort Ω(n) Θ(n2) O(n2) O(1)
Selection Sort Ω(n2) Θ(n2) O(n2) O(1)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n2) O(n)
Shell Sort Ω(n log(n)) Θ(n(log(n))2) O(n(log(n))2) O(1)
Bucket Sort Ω(n+k) Θ(n+k) O(n2) O(n)
Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k)
Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k)
Cube sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

Leave a Reply

Your email address will not be published. Required fields are marked *