Sorting

Question

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

Comments

no, bubble sort in best case take O(n) time..

because bubble sort is only sorting algorithm which checks if array is already sorted to avoid unnecessary iterations.

---

I dont think that  in standard implementation of bubble sort best case 0(n) is possible.However it can be modified to work in 0(n).Please correct me if wrong

---

Bubble sort takes O(n^2) in every case but insertion sort takes O(n) in the best case and insertion sort is an in-place algorithm.

Answer 1

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.

Comments

Best Case complexity of Bubble Sort is O(n).

Answer 2

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