Cheatsheet of Space and Time Complexities of Popular Sorting Algorithms

7 May, 2021

938 read  ·  12 hit

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

 

Algorithm

 

Best

 

Average

 

Worst

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

 

Algorithm

 

Worst

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

Cheatsheet of Space and Time Complexities of Popular Sorting Algorithms

7 May, 2021
938 read  ·  12 hit

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

 

Algorithm

 

Best

 

Average

 

Worst

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

 

Algorithm

 

Worst

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

Recommended

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

© 2021 ayedot. All Rights Reserved.

;