Cheatsheet of Space and Time Complexities of Popular Sorting Algorithms

7 May, 2021
1.21k read  ·  12 Hearts

Don't like searching one by one to find the space and time complexities of all sorting algorithms, then here is the Cheatsheet list of Time and Space Complexities of popular Sorting Algorithms like Quicksort, Mergesort, Timsort, Heapsort, Bubble Sort, Insertion Sort, Selection Sort, Tree Sort, Shell Sort, Bucket Sort, Radix Sort, Counting Sort, and Cubesort.

Time Complexities









Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2)
Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n))
Timsort Ω(n) Θ(n log(n)) O(n log(n))
Heapsort Ω(n log(n)) Θ(n log(n)) O(n log(n))
Bubble Sort Ω(n) Θ(n^2) O(n^2)
Insertion Sort Ω(n) Θ(n^2) O(n^2)
Selection Sort Ω(n^2) Θ(n^2) O(n^2)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2)
Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2)
Bucket Sort Ω(n+k) Θ(n+k) O(n^2)
Radix Sort Ω(nk) Θ(nk) O(nk)
Counting Sort Ω(n+k) Θ(n+k) O(n+k)
Cubesort Ω(n) Θ(n log(n)) O(n log(n))
Space Complexity





Quicksort O(log(n))
Mergesort O(n)
Timsort O(n)
Heapsort O(1)
Bubble Sort O(1)
Insertion Sort O(1)
Selection Sort O(1)
Tree Sort O(n)
Shell Sort O(1)
Bucket Sort O(n)
Radix Sort O(n+k)
Counting Sort O(k)
Cubesort O(n)
Programming Programming coding sorting algorithmns data structures
Comments  ·  0
You need to be Logged in to Comment. Login

More from @elitecoder


Need Help? ·  About
Terms and Conditions ·  Contact ·  Privacy

© 2021 ayedot. All Rights Reserved.