Question

Which sorting algorithm has the best asymptotic runtime complexity?

Answer 1

Algorithm

Time Complexity

Best

Average

Heapsort

Ω(n log(n))

Θ(n log(n))

Bubble Sort

Ω(n)

Θ(n^2)

Insertion Sort

Ω(n)

Θ(n^2)

Answer 2

Answer:

Insertion Sort and Heap Sort has the best asymptotic runtime complexity.

Explanation:

It is because their best case run time complexity is - O(n).

However, average case best asymptotic run time complexity is O(nlogn) which is given by- Merge Sort, Quick Sort, Heap Sort.

The worst case best run time complexity is O(nlogn) which is given by -Merge Sort and Heap Sort.