Time and Space Complexity
| Sorting Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best Case | Average Case | Worst Case | Worst Case | |
| Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Selection Sort | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Insertion Sort | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
| Quick Sort | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
| Radix Sort | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
| Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
The space complexity of Linear Search is O(1) and Binary Search is O(1).
The time complexity of linear search is O(N) while binary search has O(log2N).
Comments
Post a Comment