CMI2012-A-08

Question

You are given two sorting algorithms A and B that work in time $O(n \log n)$ and $O(n^2)$, respectively. Consider the following statements:

1. Algorithm $A$ will sort any array faster than algorithm $B$.
2. On an average, algorithm $A$ will sort a given array faster than algorithm $B$.
3. If we need to implement one of the two as the default sorting algorithm in a system, algorithm $A$ will always be preferable to algorithm $B$.

Which of the statements above are true?

• A. I, II and III
• B. I and III
• C. II and III
• D. None of them

Answer 1

Ans C)

A has sorting time faster than B , generally but not always

Because quick sort differ in worst case running time than merge sort and heap sort

Again Bubble sort, insertion sort has O(n) time complexity in best case , where in other case has O(n²) complexity

So, we cannot say Array A sort any array faster than B

Comments

Got it sir.... Thank you sir  :) This is where I do mistakes.

---

@arjun sir , i think ans is option D. if O(n^2) algo is considered as quick sort and if O(nlogn) algo is considered as merge sort then in many cases quick sort is selected because of its lower constant value effect than merge sort....

---

@Nachiket, Question here gives only worst case running time of two algorithms who's exact implementation steps are not given. We cannot assume it to be Quick sort or Merge sort. For general case, the algorithm with lesser worst case time complexity will be preferred by default.

Explanation by Arjun Sir is accurate. Hence answer is C.