Question

.You want to check whether a given set of items is sorted or not.Which of the following sorting methods will be the most efficient if it is already in sorted order?
a. Bubble sort b. Selection sort c. Insertion sort   d.Merge sort

Answer 1

• The standard Bubble sort implementation takes $O\left ( n^{2} \right )$ time in any case (though we have a modified version of it which can detect if there were any swaps made), but here we can't assume that the mentioned Bubble Sort procedure is modified.
• The Selection sort procedure is also going to take $O\left ( n^{2} \right )$ time.
• Merge Sort runs in $\Theta \left ( nlogn \right )$ time.
• The best algorithm to detect a sorted sequence is Insertion Sort. In case of sorted input, this procedure will terminate in $O\left ( n \right )$ time.

Hence option C is correct.

Comments

but best case for bubble sort is also O(n)

---

You didn't read my answer properly.When bubble sort is modified using a flag ,then only its time complexity in best case=O(n),however the standard code for bubble sort does not include the flag.Hence in all cases, the standard procedure runs in $O(n^2)$ time.We have to assume that the these questions are asked with reference to standard code of bubble sort.

---

https://en.wikipedia.org/wiki/Bubble_sort

---

check out geekforgeeks and bubble sort code in cormen book.

---

@Hitesh , thanks for the answer..could you please tell me which statement is correct here or both statements should be correct ?

1) Best case time complexity of insertion sort is $\Omega (n)$

2) Best case time complexity of insertion sort is O(n)

---

Both are correct so equivalently you can write - $\Theta(n)$

---

@Soumya , but I think , for best case time complexity  of an algorithm , we use Big-omega notation because it gives asymptotic lower bound...

---

@Ankit,
Check this -  https://cs.stackexchange.com/questions/23068/how-do-o-and-%CE%A9-relate-to-worst-and-best-case

---

@ankitgupta.1729, omega is correct. Generally we use big-oh for worst case and omega for best case...Big oh says that in worst case also ,the algorithm will not go beyond a limit.Omega says that in best case,the best you can get is n(or any other value)
....Inserting sort is also useful when most of the elements are sorted .In that case,there will be n comparisons plus some constant number of swaps...therefore time complexity can be written as omega(n)....Do upvote the original answer...