Lower bound: Decision tree and adversary argumentComparison sortDecision Tree ModelDecision tree modelLower bound: for comparison sortMaximum: O(n)Lower bound for maximumAdversary argumentSlide 9Adversary argument for maximumAdversary argument for finding both maximum and minimum.Adversary argument—four statusAdversary argument --strategyAdversary argument—proofMinimum and Maximum: 3 n/2 comparisons1Lower bound: Decision tree and adversary argument•Lower bound: (f(n)) in the worst case.•Decision tree model: –Example: for comparison sorting.•Adversary argument:–Example: find the maximum2Comparison sort•Comparison sort: –Insertion sort, O(n2), upper bound in worst case–Merge sort, O(nlg n), upper bound in worst case–Heapsort, O(nlg n), upper bound in worst case–Quicksort, O(nlg n), in average case•Question: –what is the lower bounds for any comparison sorting: i.e., at least how many comparisons needed in worst case?–It turns out: Lower bound in worst case: (nlg n), how to prove?–Merge and Heapsort are asymptotically optimal comparison sorts.3Decision Tree Model•Assumptions:–All numbers are distinct (so no use for ai = aj )–All comparisons have form ai  aj (since ai  aj, ai  aj, ai < aj, ai > aj are equivalent).•Decision tree model–Full binary tree–Internal node represents a comparison.•Ignore control, movement, and all other operations, just see comparison–Each leaf represents one possible result.–The height (i.e., longest path) is the lower bound.4Decision tree model2:31:22:31:31:3<1,2,3><1,3,2> <3,1,2><2,1,3><2,3,1> <3,2,1> >>>>>Internal node i:j indicates comparison between ai and aj.suppose three elements < a1, a2, a3> with instance <6,8,5>Leaf node <(1), (2), (3)> indicates ordering a(1) a(2) a(3).Path of bold lines indicates sorting path for <6,8,5>.There are total 3!=6 possible permutations (paths).5Lower bound: for comparison sort•The Longest path is the worst case number of comparisons. The length of the longest path is the height of the decision tree.•Theorem 8.1: Any comparison sort algorithm requires (nlg n) comparisons in the worst case.•Proof:–Suppose height of a decision tree is h, and number of paths (i,e,, permutations) is n!. –Since a binary tree of height h has at most 2h leaves,•n!  2h , so h  lg (n!)  (nlg n) (By equation 3.18). •That is to say: any comparison sort in the worst case needs at least nlg n comparisons.6Maximum: O(n)•MAXIMUM(A)1. maxA[1] 2. for i 2 to length[A]3. do if max<A[i]4. then max A[i]5. return maxRunning time: O(n), n-1 comparisons are sufficient.Similar for minimum.7Lower bound for maximum•n-1 is the upper bound of maximum,•How about the lower bound (of worst case)?–Suppose n elements are distinct.–So n-1 elements are not maximum.–Every comparison has only one loser. –Therefore at least n-1 comparisons are needed.–So lower bound is n-1.–This method is called the tournament method.•Can the decision tree is used for determining the lower bound for selection?–Any one could be the maximum, so there are n leaves (output)–Thus, the height will be lg n, –If think lg n be the lower bound, it will be wrong.–So decision tree does not apply here. –Why? ((really n leaves? Duplicate leaves!)8Adversary argument•Playing a guessing game between you and your friend. –You are to pick up a date, and the friend will try to guess the date by asking YES/NO questions.–Your purpose is forcing your friend to ask as many questions as possible.•To question “is it in winter”, your answer should be NO.•To question “is the first letter of the month’s name in the first half of the alphabet”? Your answer should be YES.•Idea: –You did not pick up a date in advance at all, but–Construct a date according to the questions. –The requirement is that the finally constructed date should be consistent to all your answers to the questions. –Looks like cheating, but it is a good way to find the lower bound.9Adversary argument•Suppose we have an algorithm we think efficient. •Image an adversary tries to prove otherwise.•At each point in the algorithm, whenever an decision (i.e., key comparison) is made, the adversary tells us the result of the decision.•The adversary chooses the answer which tries to force the algorithm work hard (i.e., do a lot of decision, or to say, the answer releases as less new information as possible).•You can think the adversary is constructing a “bad” input while it is answering the questions. The only requirement on the answers is that they must be internally consistent.•If the adversary can force the algorithm to perform f(n) steps, then f(n) is the lower bound, i.e, at least how many steps in the worst case.10Adversary argument for maximum•The adversary answers the questions as treating a[i]=i, for each i .•To the query “is a[i]<a[j]”, adversary answers YES if (and only if) i<j. •If the algorithm halts in less than n-1 comparisons and claims that the maximum is located in index k, then there will be one more non-loser (non-smaller element). Suppose the non-smaller element is located in the index j≠k •Thus, the adversary can thus demonstrate this algorithm to be incorrect by claiming that the array holds the values a[i] = i for all i ≠ j and a[j] = n+1, thus making a[k] < a[j]. A contradiction!•So the algorithm must have at least n-1 comparisons to determine the maximum.•So the previous linear scan algorithm for maximum is optimal.•If you design another algorithm, such as first divide into n/2 pairs and make comparisons to get winners, then divide the winners into pairs and make comparisons, …, the total number of comparisons is still n-1.11Adversary argument for finding both maximum and minimum.•n distinct elements, •Count each win and each lose as one unit of information.•One maximum and one minimum, so n-1 loses for maximum and n-1 wins for minimum, thus, at least 2n-2 units of information is needed.•The adversary gives the answer in the way that will give away as few as possible units of new information with each comparison.12Adversary argument—four status•Denote the key status in any moment as:–W: has won at least one comparison and never lost–L: has lost at least one comparison and never won–B: has both won and lost at least one comparison–N: has not