UD CISC 320 - Recurrence Relations, Master Theorem

Unformatted text preview:

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 inO(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 inO(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

UD CISC 320 - Recurrence Relations, Master Theorem

Download Recurrence Relations, Master Theorem
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recurrence Relations, Master Theorem and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recurrence Relations, Master Theorem 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?