edited by
489 views

1 Answer

3 votes
3 votes
 n!  <= 2^x

 Taking Log on both sides.
      log2(n!)  <= x

 Since log2(n!)  = Θ(nLogn),  we can say
      x = Ω(nLog2n)

 

Therefore, any comparison-based sorting algorithm must make at least nLog2n comparisons to sort the input array, and Heapsort and Merge Sort are asymptotically optimal comparison sorts. 

Related questions

0 votes
0 votes
1 answer
1
tusharb asked Feb 18, 2022
658 views
As we know the time complexity of solving the greedy knapsack algorithm depends mainly on the sorting algorithm used, Can we use counting sort as the sorting algorithm to...
1 votes
1 votes
1 answer
2
afroze asked Nov 4, 2021
551 views
what is significance of loop Invariant?when we use a loop in an algo we check it , if it properly runs then fix it in that, then why do check separately loop invariant ?
0 votes
0 votes
0 answers
3
1 votes
1 votes
1 answer
4