search
Log In
0 votes
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


Answer: (B)

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?

in Algorithms 192 views
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)

1 Answer

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

Related questions

0 votes
1 answer
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;
asked Jan 12, 2017 in Algorithms LavTheRawkstar 396 views
1 vote
2 answers
2
558 views
What is the worst case time complexity to find kth smallest element into an array of ‘n’ element?
asked Jan 24, 2018 in DS vishal chugh 558 views
1 vote
2 answers
3
464 views
What is the meaning of upper bound and worst case lower bound here?
asked Nov 5, 2016 in Algorithms vaishali jhalani 464 views
0 votes
3 answers
4
763 views
First read it properly. I am not asking a specific question about space complexity. Question: What is worst case space complexity of quick sort? Everywhere it is showing O(logn). My understanding about it: I know that Quick sort algorithm doesn't request extra space except for ... if partition is being done by ratio 1:n-1 which is worst case, wouldn't it be requesting for O(n) stack records?
asked Apr 21, 2018 in DS Akash Kumar Roy 763 views
...