useful mathematical techniques to compare the growth rates of different functionsit is sometimes helpful to apply the following rule proposition ( 'hopital' rule)if we have limnf (nand we have limng( +then limnf ( )/ (nlimnf ( )/ ( )where (nand (nrespectively denote the derivatives of (nand (nin deriving an upper or lower bound for summationit is often useful to split summation as followsn = = (if (in (iij+ another useful technique is to bound sum by an integral if is nondecreasing functionthenassuming the following terms are definedz - + = (xdx < ( < (xdx there is general form of recurrence relation that arises in the analysis of divide-and-conquer algorithmst (nat ( /bf ( )for constants > and proposition let (nbe defined as above then if (nis (nlogb - )for some constant then (nis th(nlogb if (nis th(nlogb logk )for fixed nonnegative integer > then (nis th(nlogb logk+ if (nis (nlogb + )for some constant and if ( / < ( )then (nis thf ( )this proposition is known as the master method for characterizing divide-andconquer recurrence relations asymptotically