Comparison of time complexities of Sorting Algorithms 

By Prof. Fazal Rehman Shamil
Last modified on March 3rd, 2022

Comparison of time complexities of Sorting Algorithms

SORTING ALGORITHM TIME COMPLEXITY SPACE COMPLEXITY
BEST CASE AVERAGE CASE WORST CASE WORST CASE
Bubble Sort Ω(N) Θ(N2) O(N2) O(1)
Insertion Sort Ω(N) Θ(N2) O(N2) O(1)
Selection Sort Ω(N2) Θ(N2) O(N2) O(1)
Heap Sort Ω(N log N) Θ(N log N) O(N log N) O(1)
Merge Sort Ω(N log N) Θ(N log N) O(N log N) O(N)
Quick Sort Ω(N log N) Θ(N log N) O(N2) O(N log N)
Count Sort Ω(N + k) Θ(N + k) O(N + k) O(k)
Bucket Sort Ω(N + k) Θ(N + k) O(N2) O(N)
Radix Sort Ω(N k) Θ(N k) O(N k) O(N + k)

 

Comparison of generations of computers

Generation? Period? Technology?
First Generation 1946-1959. Vacuum tube based
Second Generation 1959-1965 Transistor based
Third Generation 1965-1971 Integrated Circuit based
Fourth Generation 1971-1980 VLSI microprocessor based
Fifth Generation 1980-onwards ULSI microprocessor based
Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,
2. Video lectures on Youtube
3. Email is only for Advertisement/business enquiries.