Ace Test Series: Algorithms - Sorting

Question

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

(A)$n$

(B)$n^2$

(C)$nlogn$

(D)$n \space{log\space n}^2$

Answer 1

	quick sort	merge sort	selection sort	insertion sort	heap sort
worst case	O($n^{2}$)	$O(nlogn)$	O($n^{2}$)	O($n^{2}$)	O(nlogn)

so, tightest lower bound is O(nlogn)