algorithm design techniques if bk then the sum is geometric series with ratio smaller than since the sum of infinite series would converge to constantthis finite sum is also bounded by constantand thus equation ( appliest(no(am (alogb (nlogb ( if bk then each term in the sum is since the sum contains logb terms and bk implies that logb kt(no(am logb no(nlogb logb no(nk logb no(nk log ( finallyif bk then the terms in the geometric series are larger than and the second formula in section applies we obtain (nam (bk / ) + (am (bk / ) ((bk ) (nk (bk / ( proving the last case of the theorem as an examplemergesort has and the second case appliesgiving the answer ( log nif we solve three problemseach of which is half the original sizeand combine the solutions with (nadditional workthen and case applies heregiving bound of (nlog ( an algorithm that solved three half-sized problemsbut required ( work to merge the solutionwould have an ( running timesince the third case would apply there are two important cases that are not covered by theorem we state two more theoremsleaving the proofs as exercises theorem generalizes the previous theorem theorem the solution to the equation (nat( / (nk logp )where > and > is log if bk ( + (no( log nif bk (nk logp nif bk theorem  if ki= ai then the solution to the equation (ni= (ai no(nis (no(nclosest-points problem the input to our first problem is list of points in plane if ( and ( )then the euclidean distance between and is [( - ) +( - ) ] /