Answer Happy

= Suppose L = (ao, Q1, ..., On) is a list of positive integers. We say that a number a is a local minimum of L if there is some index i such that 1<i<n - 1, ai = a, Qi-1 > Qį, and ai <Qi+1. Consider the following recursive algorithm LocalMin(L), which takes as input a list L of positive integers: We consider cases depending on the length of L. If L has length 2 or less, output 0.
If L has length 3, say L = (a,b,c), check if a b and b<c If so, output b. Otherwise, output 0. If L has length greater than 3, let Lo be the list of the first [21/2+ 1 entries of L. Make a recursive call LocalMin(L) and put its output in the variable mo. If mo #0, output mo. Otherwise, let L be the list of the last ||41/27 +1 entries of L. Make a recursive call LocalMin(L) and output its output. This completes the description of LocalMin. Here are some facts which may help in your analysis of LocalMin: Suppose L is a list of integers, Lo is the list consisting of the first [12/27 + 1 entries of L, and L. is the list consisting of the last [2/2] + 1 entries of L. Fact la. Any local minimum of Lo is also a local minimum of L. Fact 1b. Any local minimum of Lis also a local minimum of L. Fact le. If Lo and L, both have no local minimum, then L does not have a local minimum. Fact 2. If n > 3, then ((n +1)/2] +1 <n. You may use the above facts in your solution without proof, but you must cite them when you do so. Now, your task: (a) (7 points) Use strong induction to prove that for all lists L of pos- itive integers, LocalMin(L) terminates, and its output (denoted by b) satisfies the following: Either b = 0 and L has no local mini- mum, or b +0 and b is a local minimum of L. (Hint: What you have to prove for the base case is different from the usual, because of the way the algorithm is structured.) (b) (2 points) Let T(n) denote the maximum number of comparison operations performed by LocalMin(L), if L has length n. Write down a recurrence relation for 7(n). (No justification needed. You can simplify this recurrence relation for asymptotic analysis if you wish. You are not asked to solve this recurrence.)