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

@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...