Question

Which sorting algorithm has the best average-case time complexity?

• A. Bubble Sort
• B. Selection Sort
• C. Quick Sort
• D. Insertion Sort

Hint:

Quick Sort is one of the most efficient sorting algorithms with an average-case time complexity of \( O(n \log n) \).

Answer 1

The Correct Option is C

Quick Sort has the best average-case time complexity of \( O(n \log n) \). It is an efficient divide-and-conquer algorithm that partitions the array into smaller sub-arrays and recursively sorts them. In the average case, it performs better than other sorting algorithms.
- Bubble Sort (A) has an average-case time complexity of \( O(n^2) \), which makes it much slower than Quick Sort in most cases.
- Selection Sort (B) also has an average-case time complexity of \( O(n^2) \).
- Insertion Sort (D) has an average-case time complexity of \( O(n^2) \), but it can perform better than other \( O(n^2) \) algorithms on small or nearly sorted arrays.
Thus, the correct answer is (C), Quick Sort with \( O(n \log n) \).