CISC320 Algorithms, Spring 2010Recurrence Relations, Master TheoremBig-O upper bounds on functions defined by a recurrence may be determined from abig-O bounds on their parts. Here is a key theorem, particularly useful when estimating thecosts of divide and conquer algorithms.Master Theorem (for divide and conquer recurrences):Let T(n) be a function defined on positive n, and having the propertyT (n) ≤(c, if n ≤ 1,aT (n/b) + f(n), n > 1,for some constants c, a > 0, b > 1, d ≥ 0, and function f(n). If f(n) is in O(nd), thenT (n) is inO(nd), if d > logb(a),O(ndlog(n)), if d = logb(a),O(nlogb(a)), if d < logb(a).We will discuss many applications of the Master theorem. First for the sake of compar-ison, here is a theorem with similar structure, useful for the analysis of some algorithms.Jokingly, call it theMuster Theorem (for subtract and conquer recurrences):Let T (n) be a function defined on positive n, and having the propertyT (n) ≤(c, if n ≤ 1,aT (n − b) + f(n), n > 1,,for some constants c, a > 0, b > 0, d ≥ 0, and function f(n). If f(n) is in O(nd), thenT (n) is inO(nd), if a < 1,O(nd+1), if a = 1,O(ndan/b), if a > 1.2Proof: Expanding the recursion by one step, we haveT (n) ≤ a( T (n − 2b) + f(n − b) ) + f(n)= a2T (n − 2b) + af(n − b) + f(n).Taking another step, we getT (n) ≤ a3T (n − 3b) + a2f(n − 2b) + af(n − b) + f(n),etc. This leads to T (n) ≤Pn/bi=0aif(n − ib) plus a constant. Since f(n − ib) is in O(n − ib)which is in O(n), we have that T (n) is in O(ndPn/bi=0ai). The homework problem 0.2finishes the job.1Remark: This theorem is written to reveal a similarity to the Master theorem. The firstcase is there for the sake of similarity. It doesn’t occur in algorithm analysis, since if a is thenumber of recursive calls, a < 1 implies no recursive calls and no need for the theorem. Thesecond case arises often. Insertion sort and modexp() are two examples at hand. The thirdcase is not so common, but applies for instance to the iconic Towers of Hanoi problem. Wegive it a quick sketch.function HanoiPuzzle(n)Input: n = height of stack of disks to be moved from one peg to another.Rules of puzzle: There are three pegs and a stack of n disks on one of the pegs. In the stackeach disk has smaller radius than the one below it. The goal of the game is to move thestack to another peg. Each move consists in moving a disk from one peg to another. A diskmay never be put on top of a smaller disk.Output: puzzle solved - stack is moved.if n = 0, returnHanoiPuzzle(n − 1) [Move n-1 disks to another peg following rules of the game.]Move one disk [Move the largest disk to the open peg (a legal move).]HanoiPuzzle(n − 1) [Move n-1 disks so as to end up on top of the largest disk.]For T(n) being the number of moves to solver HanoiPuzzle(n), the recurrence isT (n) = 2T (n − 1) + 1.In this case a = 2, b = 1, d = 0, and the theorem tells us we have 2ndisk moves necessary tosolve the Towers of Hanoi
View Full Document