algorithm design techniques more generallya samplesof elements is chosen from the elements let be some numberwhich we will choose later so as to minimize the average number of comparisons used by the procedure we find the ( ks/ )th and ( ks/ )th smallest elements in salmost certainlythe kth smallest element in will fall between and so we are left with selection problem on elements with low probabilitythe kth smallest element does not fall in this rangeand we have considerable work to do howeverwith good choice of and dwe can ensureby the laws of probabilitythat the second case does not adversely affect the total work if an analysis is performedwe find that if / log / and / log / nthen the expected number of comparisons is ( / log / )which is optimal except for the low-order term (if / we can consider the symmetric problem of finding the ( )th largest element most of the analysis is easy to do the last term represents the cost of performing the two selections to determine and the average cost of the partitioningassuming reasonably clever strategyis equal to plus the expected rank of in swhich is (nd/sif the kth element winds up in sthe cost of finishing the algorithm is equal to the cost of selection on snamelyo(sif the kth smallest element doesn' wind up in sthe cost is (nhowevers and have been chosen to guarantee that this happens with very low probability ( / )so the expected cost of this possibility is ( )which is term that goes to zero as gets large an exact calculation is left as exercise this analysis shows that finding the median requires about comparisons on average of coursethis algorithm requires some floating-point arithmetic to compute swhich can slow down the algorithm on some machines even soexperiments have shown that if correctly implementedthis algorithm compares favorably with the quickselect implementation in theoretical improvements for arithmetic problems in this section we describe divide-and-conquer algorithm that multiplies two -digit numbers our previous model of computation assumed that multiplication was done in constant timebecause the numbers were small for large numbersthis assumption is no longer valid if we measure multiplication in terms of the size of numbers being multipliedthen the natural multiplication algorithm takes quadratic time the divide-and-conquer algorithm runs in subquadratic time we also present the classic divide-and-conquer algorithm that multiplies two -by- matrices in subcubic time multiplying integers suppose we want to multiply two -digit numbersx and if exactly one of and is negativethen the answer is negativeotherwise it is positive thuswe can perform this check and then assume that xy > the algorithm that almost everyone uses when multiplying by hand requires ( operationsbecause each digit in is multiplied by each digit in if , , and , , xy , , , , , let us break and into two halvesconsisting of the most significant and least significant digits