# Highest best case implies worst case?

192 views

Which of the below given sorting techniques has highest best-case runtime complexity.
(A) Quick sort

(B) Selection sort
(C) Insertion sort

(D) Bubble sort

Explanation:
Quick sort best case time complexity is Ο(n logn)
Selection sort best case time complexity is Ο(n^2 )

Insertion sort best case time complexity is Ο(n)

Bubble sort best case time complexity is Ο(n)

Source: GeeksforGeeks

https://www.geeksforgeeks.org/gate-gate-mock-2017-question-12/

I did not understand this as best case time should be O(n) sorting method what does highest best cases mean?

0

Highest { best-case runtime (for that algorithm!) } complexity is the one which takes the longest time to complete. The question wants you to find the highest, which is the slowest algorithm from the options. So, it is obviously it is $O(n^2)$.

0
There is no meaning for highest best case.
Quick sort best case complexity O(nlogn)
Insertion sort best case: O(n), If, all elements are already sorted order then it gives result O(n)
Bubble sort best case: O(n), If, all elements are already sorted order then it gives result O(n)

According to the question answer should be option B)Selection sort with highest best case complexity ie O(n^2)

## Related questions

1
396 views
INSERTION-SORT (A, n) ⊳ A[1 . . n] for (j ← 2 to len(A) ) { key ← A[ j]; i ← j – 1 ; while (i > 0 and A[i] > key) { A[i+1] ← A[i]; i ← i – 1; } A[i+1] = key;
1 vote