Sorting N/Slide 6 Lower Bound for Sorting a different algorithm would have a different decision tree Decision tree for insertion sort on 3 elements al: a2 a2:a3 al: a3 (al,a2,a3) al: a3 (a2, a1, a3) a2: a (al,a3,a2) (a3,al,a2) (a2, a3, al (a3,a2,al) There exists an input ordering that corresponds to each root-to-leaf path to arrive at a sorted order. For decision tree of insertion sort, the longest path is O(N2)
Sorting IV / Slide 6 Lower Bound for Sorting A different algorithm would have a different decision tree Decision tree for Insertion Sort on 3 elements: There exists an input ordering that corresponds to each root-to-leaf path to arrive at a sorted order. For decision tree of insertion sort, the longest path is O(N2 )
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 case
Sorting 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