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 )