Average case-analysis:

Find for

5.4 Consider this alternate set of inputs for SEARCH: J, where for each input (lst,x) E Jn, Ist has length n, and x and the elements of lst are all between the numbers 1 and 10 (of course, lst can now contain duplicates) Show that the average-case running time of Search on this set of inputs is (1), ie., is constant with respect to the length of the input list You'll find the following formula helpful: n+1 nr Y-Y 5.4 Consider this alternate set of inputs for SEARCH: J, where for each input (lst,x) E Jn, Ist has length n, and x and the elements of lst are all between the numbers 1 and 10 (of course, lst can now contain duplicates) Show that the average-case running time of Search on this set of inputs is (1), ie., is constant with respect to the length of the input list You'll find the following formula helpful: n+1 nr Y-Y