theorem the solution to the equation (nat( / (nk )where > and is log if bk ( (no(nk log nif bk (nk if bk proof following the analysis of mergesort in we will assume that is power of bthuslet bm then / bm- and nk (bm ) bmk bkm (bk ) let us assume ( and ignore the constant factor in (nk then we have (bm at(bm- (bk ) if we divide through by am we obtain the equation % bk (bm- (bm am am- we can apply this equation for other values of mobtaining % - bk (bm- (bm- am- am- % - (bm- bk (bm- am- am- ( ( bk ( ( ( % ( we use our standard trick of adding up the telescoping equations ( through ( virtually all the terms on the left cancel the leading terms on the rightyielding % (bm bk = ( = % bk ( = thus % bk (nt( = (