chap analysis techniques note that am alogb nlogb ( the summation is geometric series whose sum depends on the ratio bk / there are three cases from equation ri /( ) constant = thust(nth(am th(nlogb because bk /awe know that bk from the definition of logarithms it follows immediately that logb we also note from equation that logb thusm logb = because am logb nk we have (nth(nlogb log nth(nk log from equation = rrm+ th(rm - thust(nth(am rm th(am (bk / ) th(bkm th(nk we can summarize the above derivation as the following theoremsometimes referred to as the master theorem theorem (the master theoremfor any recurrence relation of the form (nat( /bcnk ( cthe following relationships hold if bk th(nlogb th(nk log nif bk (nth(nk if bk