Algorithm Complexity:

Considere the following code: def search (lst, x): for item in lst: if item == x: return True return False Prove that: 5.4 Consider this alternate set of inputs for SEARCH: Jn, where for each input (lst, z) E J, lst has length n, and z and the elements of Ist are all between the numbers 1 and 10 (of course, lst can now contain duplicates). Show that the average-case running time of SBARCH on this set of inputs is 0(1), ie., is constant with respect to the length of the input list. You'll find the following formula helpful: n-1 2 The useful formula should be summation over ir^i, rather than ix