CSE310 Lecture 08 Lower Bound For Sorting Guoliang Larry Xue Department of CSE Arizona State University http www fulton asu edu xue Guoliang Xue asu edu Topics of this lecture Review of worst case running time of sorting algorithms Insertion sort Quick sort Mergesort Comparison Based Sorting Decision Tree Model Sorting Lower Bound 2 Guoliang Xue asu edu Comparison of sorting algorithms Algorithm best average worst Insertion Sort O n O n2 O n2 Quicksort O n log n O n log n O n2 Mergesort O n log n O n log n O n log n 3 Guoliang Xue asu edu Lower Bound for Sorting by Comparison sorting by comparison we use only comparisons between elements to gain order information about an input sequence a1 a2 an That is for any ai and aj we perform one of the tests ai aj ai aj ai aj to determine their relative order sorting by comparison can be viewed abstractly in terms of decision trees 4 Guoliang Xue asu edu decision algorithm tree represents the comparisons performed by a sorting each internal node of the tree represents a comparison between two elements ai and aj is ai aj or is ai aj each leaf of the tree represents a permutation of a1 a2 an The execution of the sorting by comparison algorithm corresponds to following the sequence of comparisons on the path from the root to a leaf of the decision tree 5 Guoliang Xue asu edu EXAMPLEINSERTION SORT operating on elements a1 a2 a3 a1 a2 yes no a2 a3 a1 a3 no yes a 1 a 2 a3 yes a 1 a 3 a2 no a1 a3 yes a2 a1 a3 no a3 a1 a2 a2 a3 yes a 2 a 3 a1 no a 3 a 2 a1 Each of the n permutations of the elements must appear as a leaf of the tree for the sorting algorithm to sort properly 6 Guoliang Xue asu edu More Decision Trees An example of a decision tree for using insertion sort to sort 4 elements An example of a decision tree for sorting 4 elements using quick sort Any decision tree for sorting n elements must have at least n leaf nodes Why 7 Guoliang Xue asu edu Height of a Binary Tree Minimum height of a binary tree A binary tree of height K has at most 2K 1 1 nodes At most 2k 1 nodes at level k 1 At most 2K 1 1 nodes total As a result the minimum height of a binary tree with n nodes is lg n 8 Guoliang Xue asu edu the length of the longest path from the root to a leaf in the decision tree represents the worst case number of comparisons the sorting algorithm performs worst case number of comparisons corresponds to height of the decision tree of the algorithm a binary tree with at least n leaves has height at least log n why we have that n n c n by Stirling s approximation Hence the height of a decision tree with at least n leaves is log n log n c n n log n Therefore n log n is a worst case lower bound on the number of comparisons required by a sorting by comparison algorithm on a sequence of n elements n log n is a worst case 9 lower bound on the running time Guoliang Xue asu edu An Alternative Proof of lg n n lg n n n n 1 n 1 n 2 2 1 n n 1 n 1 n 2 n 2 n 2 Therefore lg n lg n 2 n 2 n 2 lg n 2 n lg n 10 Guoliang Xue asu edu Summary Comparison based sorting has n lg n as a lower bound Decision Trees The height of a decision tree corresponds to the worst case time complexity of the corresponding sorting algorithm 11 Guoliang Xue asu edu Readings The materials covered in this lecture can be found in Section 8 1 Work on exercises 8 1 1 8 1 2 8 1 4 12 Guoliang Xue asu edu
View Full Document
Unlocking...