Computer Science, GATE

Sorting Algorithms Time Complexities

Below is a table for time complexities of all the sorting algorithms that can be used as last minute revision notes for competitive exams as well as for placements. Time complexities of algorithms in best case, average case and worst case have been listed below.

Sorting AlgorithmsBest Case ComplexityAverage Case ComplexityWorst Case Complexity
Bubble SortΩ(n)θ(n^2)O(n^2)
Selection SortΩ(n^2)θ(n^2)O(n^2)
Insertion SortΩ(n)θ(n^2)O(n^2)
Merge SortΩ(nlogn)θ(nlogn)O(nlogn)
Quick SortΩ(nlogn)θ(nlogn)O(n^2)
Radix SortΩ(nk)θ(nk)O(nk)
Bucket SortΩ(n+k)θ(n+k)O(n^2)
Heap SortΩ(nlogn)θ(nlogn)O(nlogn)
Counting SortΩ(n+k)θ(n+k)O(n+k)

If you find any information mentioned above to be incorrect then please let us know in the comment box below.

For GATE CSE last revision notes Click Here..!!