- show that randomized quick-sort runs in ( log ntime with probability at least /nthat iswith high probabilityby answering the followinga for each input element xdefine cij (xto be / random variable that is if and only if element is in subproblems that belong to size group argue why we need not define cij for let xij be / random variable that is with probability / independent of any other eventsand let log / nargue why - - = = cij ( < = = xij show that the expected value of - = = xij is ( / ) show that the probability that = = xij is at most / using the chernoff bound that states that if is the sum of finite number of independent / random variables with expected value then pr( ( / )- where argue why the previous claim proves randomized quick-sort runs in ( log ntime with probability at least / - we can make the quick-select algorithm deterministicby choosing the pivot of an -element sequence as followspartition the set into / groups of size each (except possibly for one groupsort each little set and identify the median element in this set from this set of / "babymediansapply the selection algorithm recursively to find the median of the baby medians use this element as the pivot and proceed as in the quick-select algorithm show that this deterministic quick-select algorithm runs in (ntime by answering the following questions (please ignore floor and ceiling functions if that simplifies the mathematicsfor the asymptotics are the same either way) how many baby medians are less than or equal to the chosen pivothow many are greater than or equal to the pivotb for each baby median less than or equal to the pivothow many other elements are less than or equal to the pivotis the same true for those greater than or equal to the pivotc argue why the method for finding the deterministic pivot and using it to partition takes (ntime based on these estimateswrite recurrence equation to bound the worst-case running time (nfor this selection algorithm (note that in the worst case there are two recursive calls--one to find the median of the baby medians and one to recur on the larger of and ge using this recurrence equationshow by induction that (nis (