sec recurrence relations this theorem may be applied whenever appropriaterather than re-deriving the solution for the recurrence example apply the theorem to solve ( ( / because and we find that applying case ( of the theoremt(nth( example use the theorem to solve the recurrence relation for mergesortt( ( / nt( because and we find that applying case ( of the theoremt(nth( log naverage-case analysis of quicksort in section we determined that the average-case analysis of quicksort had the following recurrencen- (ncn [ (kt( )] ( ( = the cn term is an upper bound on the findpivot and partition steps this equation comes from assuming that the partitioning element is equally likely to occur in any position it can be simplified by observing that the two recurrence terms (kand ( kare equivalentbecause one simply counts up from ( to ( while the other counts down from ( to ( this yields - (ncn (kn = this form is known as recurrence with full history the key to solving such recurrence is to cancel out the summation terms the shifting method for summations provides way to do this multiply both sides by and subtract the result