Sorting N/Slide 7 Lower bound for sorting The worst-case number of comparisons used by the sorting algorithm is equal to the depth of the deepest leaf The average number of comparisons used is equal to the average depth of the leaves a decision tree to sort n elements must have N! eaves a binary tree of depth d has at most 2d leaves > a binary tree with 2d leaves must have depth at least d the decision tree with N! leaves must have depth at least log2(N! Therefore, any sorting algorithm based on only comparisons between elements requires at least I log2 (N )I comparisons in the worst caseSorting IV / Slide 7 Lower Bound for Sorting The worst-case number of comparisons used by the sorting algorithm is equal to the depth of the deepest leaf The average number of comparisons used is equal to the average depth of the leaves A decision tree to sort N elements must have N! leaves a binary tree of depth d has at most 2 d leaves  a binary tree with 2d leaves must have depth at least d  the decision tree with N! leaves must have depth at least log2 (N!) Therefore, any sorting algorithm based on only comparisons between elements requires at least  log2 (N!)  comparisons in the worst case