GATE CSE 2004 | Question: 29

Question

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

• A. $n$
• B. $n^2$
• C. $n \log n$
• D. $n \log^2n$

Comments

The phrase "the tightest lower bound on the number of comparisons, in the worst case" means:

"We are considering all possible algorithms that can solve this problem. For each of those algorithms, we find its worst-case performance. What is the absolute best performance we can find among all of those worst cases?"

---

There is high chances of people answering either O(n) or O(n^2). But...

The question asked to find minimum no.of comparisons in worst case.

So,O(n) can't be the answer since it is in best case for insertion sort and O(n^2) can't be the answer since they asked minimum no.of comparisons.

Hence ,the minimum no.of comparisons is O(nlogn) in case of merge sort in worst case .

---

@ShamikBanerjee

then to perform hashing it will take infinite time since the slots are infinite in infinite hash table.
       -not a thug life

 

Answer 1

Am I thinking it in correct way?
Any comparision based algorithm , will take in worst case minimum nlogn comparisons right and maximum n^2

So with this we can safely say answer is C.

Answer 2

COMMENT BELOW IF YOU HAVE ANY DOUBT