Sorting N/Slide 8 Lower Bound for Sorting log2(N])=log(N(N-1)(N-2)…(2)(1) logN+log(N-1)+log(N一2)+…+log2+log1 log N +log(N-1)+log(N-2)+ .+log(N/2) N log w g &(Nlog N) Any sorting algorithm based on comparisons between elements requires Q2(N log N comparisonsSorting IV / Slide 8 Lower Bound for Sorting Any sorting algorithm based on comparisons between elements requires (N log N) comparisons