Example 1.9:

1.23 "The median of an ordered set is an element such that the number of elements less than the median is within one of the number that are greater, assuming no ties. a. Write an algorithm to find the median of three distinct integers a, b, and c. b. Describe D. the set of inputs for your algorithm. in light of the discussion in Sec- tion 1.4.3 following Example 1.9. c. How many comparisons does your algorithm do in the worst case? On the average? d. How many comparisons are necessary in the worst case to find the median of three numbers? Justify your answer. Finally, we combine the cases in which K is in the array and is not in the array. Letq be the probability that K is in the array. By the law of conditional expectations (Lemma 1,2); A(n) = Pr(succ) Asuce(n) + Prifail) A fait(n) = 4 ((n + D)) + (1 - 4)n = n(1 - 9) + q. If y = 1, that is, if K is always in the array, then Ain) = (2+1)/2, as before. If a = 1/2 that is, if there is a 50-50 chance that K is not in the array, then A(n) = 3 11/4 + 1/4: roughly three-fourths of the entries are examined. This concludes Example 1.9. Example 1.9 illustrates how we should interpret Dx, the set of inputs of size n. Rather than consider all possible arrays of names, numbers, or whatever, that could occur as inputs. we identify the properties of the inputs that affect the behavior of the algorithm: in this case. whether K is in the acay at all and, if so, where it appears. An element in D, may be thought of as a set (or equivalence class) of all arrays and values for K such that K occurs in the specified place in the array (or not at all). Then (1) is the number of operations done for any one of the inputs in