GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
90 views

I answered this as $O(n^2)$ considering the question asks for best worst case of all inplace sorting algorithms.

asked in Algorithms by Boss (8.7k points)   | 90 views
quetion ask best case for any inplace sorting algorithm . Bubble sort will take O(n).

2 Answers

+1 vote

O(n) is right 

BEST CASE OF INSERTION SORT

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

answered by Active (1.3k points)  
Best Case complexity of Bubble Sort is O(n).
+1 vote

Bubble sort, as well as Insertion sort both, will give o(n) in its best case: in bubble sort assumption is made that the passes will be stopped on the same instance when the elements are sorted. While in Insertion sort assumption is that the elements are already sorted or almost sorted

answered by (407 points)  


Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1502 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1416 Points

  5. Niraj Singh 2

    1391 Points

  6. Debashish Deka

    1246 Points

  7. Rupendra Choudhary

    1194 Points

  8. rahul sharma 5

    1158 Points

  9. Arjun

    956 Points

  10. srestha

    950 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1386 Points

  3. junaid ahmad

    502 Points

  4. Debashish Deka

    414 Points

  5. sudsho

    410 Points


23,373 questions
30,079 answers
67,406 comments
28,396 users