 Assume insertion sort is used to sort each bucket, then the third step costs formula_5, where formula_6 is the length of the bucket indexed formula_7.Since we are concerning the average time, the expectation formula_8 has to be evaluated instead.Let formula_9 be the random variable that is formula_10 if element formula_11 is placed in bucket formula_7, and formula_13 otherwise.