Comparison of time complexities of Sorting Algorithms
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 |