sorting average-case analysis this is the most difficult part for the average casewe assume that each of the sizes for is equally likelyand hence has probability / this assumption is actually valid for our pivoting and partitioning strategybut it is not valid for some others partitioning strategies that do not preserve the randomness of the subarrays cannot use this analysis interestinglythese strategies seem to result in programs that take longer to run in practice with this assumptionthe average value of ( )and hence ( )is ( /nn- = (jequation ( then becomes - (nt(jcn ( = if equation ( is multiplied by nit becomes - nt( (jcn ( = we need to remove the summation sign to simplify matters we note that we can telescope with one more equationn- ( ) ( (jc( ) ( = if we subtract equation ( from equation ( )we obtain nt( ( ) ( ( cn ( we rearrange terms and drop the insignificant - on the rightobtaining nt( ( ) ( cn ( we now have formula for (nin terms of ( only again the idea is to telescopebut equation ( is in the wrong form divide equation ( by ( ) (nt( + + ( now we can telescope ( ( - ( ( - - - ( ( ( ( (