-
Notifications
You must be signed in to change notification settings - Fork 2
Time Complexity and Space Complexity Overview for different algorithms
Praveen Kumar Anwla edited this page Apr 28, 2024
·
2 revisions
Q1: Can you please share the Time complexity for the following cases: Best case, Average Case, Worst Case for below algorithms: Bubble Sort, Selection Sort, Insertion Sort, Shell sort, Quick Sort, and Merge Sort?
Ans: Here's a table listing the time complexities of the mentioned sorting algorithms: Certainly! Here's a table summarizing the time complexity and space complexity for the specified algorithms:
| Algorithm | Best Case Time Complexity | Average Case Time Complexity | Worst Case Time Complexity | Space Complexity |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Shell Sort | O(n log^2 n) | O(n^1.25) | O(n^2) | O(1) |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
Note:
- "n" represents the number of elements in the array.
- Time complexity is presented using Big O notation.
- Space complexity refers to the additional memory space required by the algorithm, excluding the input array.
It's worth noting that while these complexities represent the general behavior of the algorithms, practical performance can vary based on factors like input data characteristics, implementation details, and hardware architecture.