the following rule proposition ( 'hopital' rule)if we have limn- (nand we have limn- ( +then limn- ( )/ (nlim nf'( )/ '( )where '(nand '(nrespectively denote the derivatives of (nand (nin deriving an upper or lower bound for summationit is often useful to split summation as followsanother useful technique is to bound sum by an integral if is nonde-creasing functionthenassuming the following terms are definedthere is general form of recurrence relation that arises in the analysis of divide-andconquer algorithmst(nat( /bf( )for constants > and > proposition let (nbe defined as above then if (nis (nlog -efor some constant then (nis th(nlog if (nis th(nlog alogkn)for fixed nonnegative integer > then (nis log th( logk+ if (nis ohm(nlog )for some constant (nisth( ( ) and if ( / <cf( )then this proposition is known as the master method for characterizing divide-andconquer recurrence relations asymptotically