bucket_sort (anotes length [ for to do insert [iinto list [na[ ] for to - do sort list with insertion sort concatenate the lists [ ] [ ] [ - together in order examplegiven input array [ the array [ of sorted lists or buckets after line bucket holds values in the interval [ / ( + )/ the sorted output consists of concatenation in order of the lists first [ then [ then [ and the last one is [ analysis all lines except line take (ntime in the worst case we can see inspection that total time to examine all buckets in line is ( - (nthe only interesting part of the analysis is the time taken by insertion sort in line let ni be the random variable denoting the number of elements in the bucket [isince the expected time to sort by insertion_sort is ( )the expected time to sort the elements in bucket [iis [ ( ni) ( [ ni]thereforethe total expected time to sort all elements in all buckets is - = ( [ ni] - = ( [ ni]( in order to evaluate this summationwe must determine the distribution of each random variable we have elements and buckets the probability that given element falls in bucket [iis / probability / note this problem is the same as that of "balls-and-binproblem lovely professional university