chap internal sorting graph (nn log nf (nn and (nn in the range < < to visually compare their growth rates typicallythe constant factor in the running-time expression for an implementation of insertion sort will be less than the constant factors for shellsort or quicksort how many times greater can the constant factor be for shellsort to be faster than insertion sort when how many times greater can the constant factor be for quicksort to be faster than insertion sort when imagine that there exists an algorithm splitk that can split list of elements into sublistseach containing one or more elementssuch that sublist contains only elements whose values are less than all elements in sublist for < if kthen sublists are emptyand the rest are of length assume that splitk has time complexity (length of lfurthermoreassume that the lists can be concatenated again in constant time consider the following algorithmlist sortk(list llist sub[ ]/to hold the sublists if ( length( splitk(lsub)/splitk places sublists into sub for ( = <ki++sub[isortk(sub[ ])/sort each sublist concatenation of sublists in subreturn (awhat is the worst-case asymptotic running time for sortkwhy(bwhat is the average-case asymptotic running time of sortkwhy here is variation on sorting the problem is to sort collection of nuts and bolts by size it is assumed that for each bolt in the collectionthere is corresponding nut of the same sizebut initially we do not know which nut goes with which bolt the differences in size between two nuts or two bolts can be too small to see by eyeso you cannot rely on comparing the sizes of two nuts or two bolts directly insteadyou can only compare the sizes of nut and bolt by attempting to screw one into the other (assume this comparison to be constant time operationthis operation tells you that either the nut is bigger than the boltthe bolt is bigger than the nutor they are the same size what is the minimum number of comparisons needed to sort the nuts and bolts in the worst case