0 votes 0 votes The tightest lower bound on the number of swaps, in the worst case, for comparison-based sorting is of the order of __________. Algorithms sorting algorithms + – Pabitra Sahoo asked Sep 12, 2021 edited Sep 26, 2021 by Arjun Pabitra Sahoo 489 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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. Vishal_kumar98 answered Sep 25, 2021 Vishal_kumar98 comment Share Follow See all 0 reply Please log in or register to add a comment.