CSE310 Lecture 08: Lower-Bound For SortingTopics of this lectureComparison of sorting algorithmsSlide 3Slide 4Slide 5More Decision TreesHeight of a Binary TreeSlide 8An Alternative Proof of lg(n!) = (n lg(n))[email protected] Lecture 08:CSE310 Lecture 08:Lower-Bound For SortingLower-Bound For SortingGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://www.fulton.asu.edu/[email protected] of this lectureTopics of this lectureReview of worst-case running time of sorting algorithmsInsertion sortQuick sortMergesortComparison Based SortingDecision Tree ModelSorting Lower [email protected] of sorting algorithmsComparison of sorting algorithmsAlgorithm [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)][email protected]= Lower Bound for Sorting by Comparison =• sorting by comparison: we use only comparisons between elementsto gain order information about an input sequence <a1, a2, …, an>.That is, for any ai and aj , we perform one of the testsai = aj ?ai > aj ?ai < aj ?to determine their relative order.• sorting by comparison can be viewed abstractly in terms of decision [email protected]• decision tree: represents the comparisons performed by a sorting algorithm.- each internal node of the tree represents a comparisonbetween 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 [email protected] operating on elements <a1, a2, a3>a1 < a2?yes no a2 < a3? a1 < a3? no no yes yes< a1, a2, a3 > a1 < a3? < a2, a1, a3 > a2 < a3? yes no yes no< a1, a3, a2 > < a3, a1, a2 > < a2, a3, a1 > < a3, a2, a1 >• Each of the n! permutations of the elements must appear as a leaf of the tree, for the sorting algorithm to sort [email protected] Decision TreesMore Decision TreesAn example of a decision tree for using insertion sort to sort 4 elementsAn 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. [email protected] of a Binary TreeHeight of a Binary TreeMinimum height of a binary treeA binary tree of height K has at most 2K+1-1 nodes.At most 2k-1 nodes at level k-1At most 2K+1-1 nodes total.As a result, the minimum height of a binary tree with n nodes is lg(n)[email protected]• 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 heightof 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 ofcomparisons required by a sorting (by comparison) algorithm on asequence of n elements. (n log n) is a worst-case lower bound on the running time of any such [email protected] Alternative Proof of lg(n!) = An Alternative Proof of lg(n!) = (n 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))[email protected]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 [email protected]The materials covered in this lecture can be found in Section 8.1.Work on exercises 8.1-1, 8.1-2,
View Full Document
Unlocking...