### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Analysis of Algorithms CMPS 201

UCSC

GPA 4.0

### View Full Document

## 44

## 0

## Popular in Course

## Popular in ComputerScienence

This 21 page Class Notes was uploaded by Dr. Elyssa Ratke on Monday September 7, 2015. The Class Notes belongs to CMPS 201 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 44 views. For similar materials see /class/182274/cmps-201-university-of-california-santa-cruz in ComputerScienence at University of California - Santa Cruz.

## Popular in ComputerScienence

## Reviews for Analysis of Algorithms

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/07/15

CS 201 Schlag Winter 99 January 12 Handout 1 CS 201 Quick reference guide to solving recurrences The recipes in this handout for solving linear recurrences can be found in BESS The first section deals with linear recurrences and the other two sections present techniques which can often be used to transform nonlinear recurrences into linear ones Additional references on solving recurrences and the derivation of the characteristic equation are also given Linear Recurrences In this section three cases are presented each more general than the preceding case Case 1 Suppose first that you are given a recurrence of the form Tn 2 61Tn 7 1 62Tn 7 2 kan 7 k 1 with 1 initial conditionsie values for T Tk 7 1 The characteristic equation for this recurrence is Tk 7 blikil 7 121sz 7 7 bk 2 0 2 If 71 72 W are distinct roots of the characteristic equation then the recurrence has a solution of the form a xquot a xquot Tl Tnc171 c272 ck7k for some choice of constants 102 ck These constants can be determined from the 1 initial conditions Example 1 Tn 2 7Tn 7 l 7 STU 7 2 T 2 2 T12 7 Characteristic equation 7 71 5 2 1 7 5T 7 1 2 0 General form of solution Tn 2 016quot 021quot 2 016quot 2 Constraints for constants T 2 2 2 cl c2 Tl 2 7 2 501 02 Solution for constants c1 2 1 and 2 2 1 Solution Tn 2 5quot 1 El subsection3ase 2 When the roots of the characteristic equation Equation 2 are not distinct each time a root is repeated it is accompanied by the next highest power of n in the general form of the solution That is if there are h distinct roots 71 72 7 and MI is the multiplicity of the 2 root 7 then the solution has the form ml mg m mh J21quot J21 j71n j71n Tn E own 71 2 czvjn 72 E Mn 7 awn 7 j1 j1 j1 j1 There are m1 1 m2 1 7th 2 k constants which can again be determined from the 1 initial conditions Example 2 Tn 2 3Tn 7 1 7 1Tn 7 3 T 2 71 T1 2 2 T2 2 5 Characteristic equation 1 5 2 312 x1 2 z 1r 2 2V 2 0 General form of solution Tn 2 0171quot 1 022quot 03712quot Constraints for constants T 2 71 2 i1 2 T1 2 2 7C1 202 203 T2 2 5 2 i1 402 803 Solution for constants i1 2 72 i2 2 72 and i3 2 2 Solution Tn 2 72 71quot 7 2 2quot 1 2712 1 2 72 71quot 2n 7 12quot El Case 3 If the recurrence in Equation 1 contains some terms of the form Cquotp7l where is a constant1 and 1171 is a polynomial in n then additional roots are added to the characteristic equation Specifically when the recurrence is of the form Tn 2 61Tn 7 1 62Tn 7 2 kan 7 k cfp1n c p271 cfp m where 6162 c are constants and 111112 6 are polynomials in n then the characteristic equation is 11quot 7 blmk l 7 1121192 7 7 bkr 7 61 ll1r 7 62 121r 7 65 20 Here It if the degree of pn The general form of the solution is the same as in the previous case however there are now more than k constants to resolve The additional 11 1 12 1 15 1 initial values needed to resolve these constants can be obtained by plugging into the recurrence This is how the m 39 of the p U 39 1 in the reerrrrerree in uence its solution 1not necessarily 27182818 Example 3 Tn 2 2Tn 7 1 1 71 2quot T 2 0 The two extra terms in the form 6quot71 are 1quotn and 2quot2 Characteristic equation x 7 2r 7 111z 7 2 2 z 7 1H2 7 22 20 General form of solution Tn 2 011quot 02 711quot 032quot 7 04712quot Three additional values can be obtained from the recurrence T1 2 T2 2 20 T3 2 39 Constraints for constants T 2 0 2 i1 3 T1 2 2 i1 02 203 204 T2 2 20 2 i1 202 403 7 8C4 T3 2 59 2 i1 302 803 7 2104 Solution for constants i1 2 72 i2 2 71 i3 2 2 and C4 2 2 Solution Tn 2 72 7 71 2quot1n 1 I Domain Transformations aka Change of Variable A recurrence relation for Tn might involve previous terms which are not within a fixed range of 71 Domain transformations can sometimes be used to substitute a function for the argument of the relation and remedy this situation Specifically given a recurrence relation for Tn in terms of Tfn Tffn Tfkn the idea is to select a function gm with the property that fgm 2 gm 7 1 Substituting 9m for 71 gives a recurrence relation for Tgm in terms of Tfgm Tffgm Tfkgm and these terms can be rewritten as Tgm 7 1 Tgm 7 2 Tgm 7 19 A linear recurrence relation for Sm in terms of Sm7 1 Sm7 2 Sm7 k is obtained by equating Sm with Tgm A solution for Sm can be transformed back into a solution for Tn by substituting g 1n for m That is since Tgm 2 Sm Tn 2 S39g 1n Example 4 Tn 2 7T 7 076 r1 2 2 r2 2 7 In this case fn 2 and by selecting 9m 2 2 we obtain fgm 2 2 2 2quot1 1 2 gm 7 1 By equating n with 2 we obtain 2quot Tlt2mgt 2 m 2 Let Sm 2 T2m The recurrence for Sm is 1 2m 7lt5r 1 2 7r2m17lt5r2m2 Sm 2 75m 7 1 7 59m 7 2 30 2 T1 2 2 31 2 T2 2 7 Note that the initial conditions for 51771 were also transformed This recurrence was solved in Example 1 its solution is 1771 2 5m 1 The inverse of 9771 2 2m is g 171 2 log2 71 The solution for 1171 is 1171 2 5197101 2 Slog2 71 2 610quot 1 2 71l g26 1 Range Transformations A recurrence relation may not always be linear For example there might be a product of terms in the relation A range transformation attempts to apply a function to the recurrence to make it linear Specifically given a recurrence relation for 1171 in terms of 1171 7 1 1171 7 2 T717 k the idea is to find a function fr such that fT71 is a linear combination of fT717 1 fT717 2 fT71 7 19 Then by equating W171 with fT71 we obtain a linear recurrence relation which can be solved using the methods in the first section Since 1171 is f 1W171 a solution for W171 can be transformed back into a solution for 1171 Example 5 1171 7 13 1171 2 2 T 2 2 T1 2 2 In this case by selecting fr 2 log2 7 we obtain Km 2 logmn 2 log2 2 log2T717 13 7 log2 1171 7 22 2 31og211717 172log2T71721 2 3fT717172fT71721 If we let W171 2 f 1171 and the we obtain the following recurrence for W171 W171 2 3W1717 l 7 2W1717 2 l which has characteristic equation 7 2 lr 2 2r 2 1 2 7 2 12r 2 2 2 0 The general form of the solution is W171 2 011quot 02711quot 032quot Since there are three constants one additional initial value must be obtained from the recurrence for solving the constants r1 5 223 39r2 quot T222 2721 CMPS 201 Analysis of Algorithms Spring 2007 Recurrence Relations When analyzing the run time of recursive algorithms we are often led to consider functions Tn which are de ned by recurrence relations of a certain form A typical example would be 0 n1 Hquot TIn2JTI n2I dn 1 gt1 where c d are xed constants The speci c values of these constants are important for determining the explicit solution to the recurrence Often however we are only concerned with nding an asymptotic upper lower or tight bound on the solution We call such a bound an asymptotic solution to the recurrence In the above example the particular constants c and d have no effect on the asymptotic solution We may therefore write our recurrence as n1 T 91 n TQnZJTl n2 l n n gt1 In what follows we ll show that a tight asymptotic solution to the above recurrence is Tn nlog n We will study the following methods for solving recurrences o Substitution Method This method consists of guessing an asymptotic upper or lower bound on the solution and trying to prove it by induction Recursion Tree Method Iteration Method These are two closely related methods for expressing Tn as a summation which can then be analyzed A recursion tree is a graphical depiction of the entire set of recursive invocations of the function T The goal of drawing a recursion tree is to obtain a guess which can then be veri ed by the more rigorous substitution method Iteration consists of repeatedly substituting the recurrence into itself to obtain an iterated ie summation expression Master Method This is a cookbook method for determining asymptotic solutions to recurrences ofa speci c form The Substitution Method We begin with the following example T 2 1Snlt3 70 3TLn3Jn n23 We will see later that Tn nlogn but for the time being suppose that we are able to guess somehow that Tn Onlogn In order to prove this we must nd positive numbers 0 and n0 such that Tn S cnlogn for all n 2 no If we knew appropriate values for these constants we could prove this inequality by induction Our goal then is to determine 0 and no such that the induction proof will work In what follows it will be useful to take log to mean logo We begin by mimicking the induction step IId to find c Let ngt no and assume TkScklogk for all k in the range no S k lt n In particular when k n3J we have Tn3JS cn3Jlogn3J We must show that Tn S cnlogn Observe Tn 3Tn3J n by the recurrence for T S 3cn3Jlogn3J n by the induction hypothesis S 3cn3logn3 n since LxJ S x for all x cnlogn l n cnlogn on n To obtain Tn S cnlogn we need to have cnn S 0 which will be true if c 2 1 Thus as long as c is chosen to satisfy the constraint 0 Z l the induction step will go through It remains to determine the constant no The base step requires Tno S cno logno This can be viewed as a single constraint on the two parameters c and no which indicates that we have some freedom in choosing them In other words the constraints do not uniquely determine both constants so we must make some arbitrary choice Choosing no 3 is algebraically convenient This yields T3 S 30 whence c 2 T33 Since T3 9 using the recurrence we have the constraint 0 Z 3 Clearly if we choose 0 3 both constraints c 21 and c 2 3 will be satisfied It is important to note that we have not proved anything yet Everything we have done up to this point has been scratch work with the goal of finding appropriate values for c and no It remains to present a complete induction proof of the assertion Tn S 3nlogn for all n 2 3 Proof 1 Since T3 3TL33J3 3T13 323 9 and 3 3log3 9 the base case reduces to 9 s 9 which is true II Let n gt 3 and assume for all k lt n that Tk S 3k logk Then Tn 3Tn3J n by the recurrence for T S 3 3n3Jlogn3J n by the induction hypothesis letting k n3J S 9n3logn3 n since LxJ S x for all x 3nlogn l n 3nlogn 2n S 3nlogn It now follows that Tn S 3nlogn for all n 2 3 It is a somewhat more difficult exercise to prove by the same technique that Tn Qnlogn and hence Tn nlogn Exercise Determine positive numbers 0 and no such that Tn Z cnlogn for all n 2 no Hint Use the following facts 1 LxJ gt x l and 2 log3 LxJ Z log3 x l for x 2 32 With some effort its possible to show that c 14 and no 4 work The next example illustrates one complication that can arise in the substitution method Define Tn by the recurrence T 1 n1 0 2TLn2J1 n22 We guess that Tn On To prove this guess we attempt to nd positive constants c and no such that Tn S on for all n 2 no As before we proceed by mimicking the induction step Let n gt no and assume for all k in the range no S k lt n that Tk S ck In particular for k n2J we have Tn2JS cn2J and thus Tn 2Tn 2Jl by the recurrence for Tn S 2cn 2Jl by the induction hypothesis S 2cn 2 1 on l Our goal is to determine 0 so that the induction step is feasible We need to reach the conclusion that Tn S on and to do this we must determine a number 0 such that cnl S on But this inequality is obviously false for all positive c Apparently the induction step cannot be made to work which might lead us to believe that our guess is incorrect Actually Tn On is correct as can be seen by other methods so we take a different approach Our trick is to subtract a lower order term from the right side of the inequality we wish to prove To be precise we seek positive constants c no and b such that Tn S cn b for all n 2 no Observe that this inequality also implies Tn On by a result proved in the handout on asymptotic growth rates It may seem counterintuitive to attempt to prove an inequality which is stronger than the one that failed but notice that this strategy allows us to use a stronger induction hypothesis Again let ngt no and assume for all k in the range no Sklt n that TkS ck b and in particular Tn2JS cn2J b Thus Tn 2Tn 2Jl by the recurrence for Tn S 2cn 2J bl by the induction hypothesis S 2cn2 bl since LxJSx on 2b l Ifwe take b 1 then Tn S cn b as desired For the base case let no 1 We must show Tl S cl l which says cZTll 2 Thus we may set no 1 c2 and bl Exercise Use induction to prove that Tn S 211 l for all n 2 l whence Tn 0n Exercise Referring to the previous example use the substitution method to show that Tn Qn and therefore Tn n The Recursion Tree Iteration Method The recursion tree method can be used to generate a good guess for an asymptotic bound on a recurrence This guess can then be veri ed by the substitution method Since our guess will be veri ed we can take some liberties in our calculations such as dropping oors and ceilings or restricting the values of 71 Let us begin with the example T 1 lSnlt3 70 2TLn3Jn 7123 Each node in a recursion tree represents one term in the calculation of Tn obtained by recursively substituting the expression for T into itself We construct a sequence of such trees of increasing depths 0 11 tree 1st tree 2quot 1 tree Tn n n Tn3 Tn3 n3 Tn32 Tn32 Tn32 Tn32 3ml tree n n3 n3 rt32 rt32 rt32 rt32 Tn33 Tn33 Tn33 Tn33 Tn33 Tn33 Tn33 Tn33 By summing the nodes in any one of these trees we obtain an expression for Tn After k iterations of this process we reach a tree in which all bottom level nodes are Tn3k kth tree n n3 n3 nlt rt32 rt32 rt32 Tn3k Tn3k Tn3k Rnst TotBk Note that there are 2 nodes at depth 139 each of which has value 713 for 0 St S k l The sequence of trees terminates when all bottom level nodes are Tl ie when n3k 1 which implies k log3n The number of nodes at this bottom level is therefore 2k 21 53 quot10332 Summing all nodes in the nal recursion tree gives us the following expression for Tn krl Tn22 n3 n1 532T1 10 nE23 quot10532 Ta quot10332 1 23 3nl 23k nlog3ltz If we seek an asymptotic upper bound we may drop the negative term to obtain Tn S 3n n1 532 Since log3 2 lt1 the first term dominates and so we guess Tn 0n Exercise Prove that this guess is correct using the substitution method It is sometimes possible to push these computations a little further to obtain an asymptotic estimate directly with no simplifying assumptions We call this the iteration method We illustrate on the very same example T 1 1Snlt3 70 2TLn3Jn 7123 Here we do not assume that n is an exact power of 3 and keep the oor Substituting this expression into itself ktimes yields Tnn2TLn3J n 2Ln3J2TLLn3J3J n2Ln3J2ZTLn32j n2Ln3J22ln32J2T 7132 j3j n2Ln3J22n32J 23Tln33 161 22 113 2kTLn3kj 10 The process must terminate when k is chosen so that IS Lil3k Jlt 3 which implies lSn3k lt3 3k snlt3k1 kSlog3nltkl k Llogxnu 161 With this value of k we have TQn3kjl whence Tn22 n3 J 2k This expression in 10 essence converts the computation of Tn from a recursive algorithm to an iterative algorithm which is why we call this the iteration method This summation can now be used to obtain asymptotic upper and lower bounds for Tn Tnk12 rt3 2k 10 k S 2112 rt3 21 53 since LxJS x 10 161 11223 111 0 1 23k quot10332 1 23 3nl 23k 111 S 3n 711 07 W 7 dropping the negative term since log3 2 lt 1 Thus Tn 0n has been proved Note that our proof is rigorous since at no point have we made any simplifying assumptions such as n being an exact power of 3 Therefore there is no need to verify Tn 0n by another method such as substitution In a similar fashion one can show Tn Qn Tnk12 lit3 2k 1 k z Zz n3 1 21 34 1 since LxJgt x l 111 HO 10 1H 1 1H 1 1 1032 n 23 22 En 3 10 10 k Z 22 11 grim replacing the rst sum by 1 Zn 21 53 1 inm gzm since LxJSx 71 1 171mg 2 Qn since log3 2 lt 1 We ve shown Tn 901 and since Tn 0n we now have Tn n The iteration method can even be used to nd exact solutions to some recurrences as opposed to the asymptotic solutions we have been satis ed with up to now For example de ne the function Tn by T0 Tl 5 and Tn Tn 2 n for n 2 2 Iterating ktimes we nd Tn nTn 2 nn 2Tn 4 nn 2n 4Tn 6 Eat 2i Tn 2k as H Ho kil n ZZi Tn 2k 10 n Tn 2k kn kk 1 Tn 2k u o This process must terminate when k is chosen so that either 71 2k 0 or 71 2k 1 which is where the recurrence bottoms out39 so to speak This implies 0Sn 2klt2 2kSnlt2k2 ks ltk1 2 kLn2J Thus if k n2J we have Tn 2k 5 and therefore the exact solution to the above recurrence is given by Tn Lit2 n Ln2JLn2J 1 5 The asymptotic solution is now readily seen to be Tn nz Exercise De ne Tn by Tl 0 and Tn Tn2Jl for n 2 2 Recall this was example 3 in the induction handout Use the iteration method to show Tn lgnJ for all n whence Tn logn The Master Method This is a method for nding asymptotic solutions to recurrences of the form Tn aTnb fn where a Z l b gt1 and the function f n is asymptotically positive Here Tn b denotes either Tn bl or Tl n b l and it is understood that Tn l for some nite set of initial terms Such a recurrence describes the run time of a divide and conquer algorithm which divides a problem of size n into a subproblems each of size n b In this context f n represents the cost of doing the dividing and recombining Master Theorem Let a Z l b gt1 fn be asymptotically positive and let Tn be de ned by Tn aTnbfn Then we have three cases 1 If fn 0nl g 395 for some 8 gt 0 then Tn nl g 2 If fn nl g then Tn nl g logn 3 If fn Qnl g for some 8 gt 0 and if afnb S cfn for some 0 lt 0 lt1 and for all suf ciently large n then Tn fn 103MB Remarks In each case we compare f n to the polynomial n and the solution is determined by which function is of an asymptotically higher order In case 1 numb log a is polynomially larger than f n and the solution is in the class n In case 3 f n is polynomially larger and an additional regularity condition is met so the solution is f n In case 2 the functions are asymptotically equivalent and the solution is in the class nl g logn which is the same as fnlogn To 105MB say that n is polynomially larger than f n as in 1 means that f n is bounded above by a function which is smaller than nl gbm by a polynomial factor namely n5 for some 8 gt 0 Note that the conclusion reached by the master theorem does not change if we replace f n by a function asymptotically equivalent to it For this reason the recurrence may simply be given as Tn aTnb fn Notice also that there is no mention of initial terms It is part of the content of the master theorem that the initial values of the recurrence do not effect it s asymptotic solution A few Adversary Arguments n Theorem At least 2 adjacency questions are necessary in worst case to determine whether a graph G on n vertices is connected Recall by adjacency question we mean a question of the form is vertex u adjacent to vertex v Proof Consider any algorithm for this problem and start it on an unspeci ed input graph G with n vertices The Daemon s strategy is to answer no to any edge probe unless that answer would prove that G is disconnected More precisely the Daemon maintains two edge sets X and Y where initially Y n is empty and X contains all 2 edges in K n the complete graph on n vertices The Daemon then performs the following algorithm when an edge e is probed Probegel if X e is connected X X e answer No else Y lt Ye answer Yes 9959 Here we abuse notation slightly and identify the edge setX with the subgraph of K 1 consisting of the edges inX together with all vertices in K n and similarly for Y Observe that at all times Y Q X and the set X Y consists of precisely those edges of K n which have not yet been probed Furthermore bothX and Y are consistent with the Daemon s entire sequence of answers since whenever the answer yes is given that edge is added to Y and remains in X while if no is given the corresponding edge is removed fromX and is not added to Y The following invariants are maintained over any sequence of edge probes a The subgraphX is always connected This is obvious from the construction b If X contains a cycle then none of it s edges belong to Y Proof Deleting an edge from that cycle would leave X connected and so that edge could not have been added to Y c It follows from b that Y is acyclic d If Y i X then Y is disconnected Proof Assume to get a contradiction that Y is connected Then being acyclic Y is atree Since Y i X there exists an edge e EX with 6 Y Ife were added to Y it would form a cycle with some of the other edges in Y This is a well known and obvious property of trees joining vertices by a new edge creates a unique cycle Since Y Q X that cycle is also contained inX In other words X contains a cycle consisting of 6 together with some edges in Y This contradicts remark b above The only way to avoid this contradiction is to conclude that Y is disconnected Now suppose the algorithm halts and returns a verdict connecteddisconnected after probing fewer n than 2 edges Then at least one edge of Kn was not probed hence X Y i Q and therefore Y X Now d tells us that Y is disconnected and by a X is connected Since both graphs are l CMPS 201 Analysis of Algorithms Spring 2007 Recurrence Relations When analyzing the run time of recursive algorithms we are often led to consider functions Tn which are de ned by recurrence relations of a certain form A typical example would be 0 n1 Hquot Tln2JTl n 2 dn n gt1 where c d are xed constants The speci c values of these constants are important for determining the explicit solution to the recurrence Often however we are only concerned with nding an asymptotic upper lower or tight bound on the solution We call such a bound an asymptotic solution to the recurrence In the above example the particular constants c and d have no effect on the asymptotic solution We may therefore write our recurrence as T 1 n1 739 Tln2JTl n 2 n n gt1 In what follows we ll show that a tight asymptotic solution to the above recurrence is Tn nlog n We will study the following methods for solving recurrences o Substitution Method This method consists of guessing an asymptotic upper or lower bound on the solution and trying to prove it by induction Recursion Tree Method Iteration Method These are two closely related methods for expressing Tn as a summation which can then be analyzed A recursion tree is a graphical depiction of the entire set of recursive invocations of the function T The goal of drawing a recursion tree is to obtain a guess which can then be veri ed by the more rigorous substitution method Iteration consists of repeatedly substituting the recurrence into itself to obtain an iterated ie summation expression Master Method This is a cookbook method for determining asymptotic solutions to recurrences ofa speci c form The Substitution Method We begin with the following example T 2 1Snlt3 70 3TLn3Jn n23 We will see later that Tn nlogn but for the time being suppose that we are able to guess somehow that Tn Onlogn In order to prove this we must nd positive numbers 0 and n0 such that Tn S cnlogn for all n 2 no If we knew appropriate values for these constants we could prove this inequality by induction Our goal then is to determine 0 and no such that the induction proof will work In what follows it will be useful to take log to mean logo We begin by mimicking the induction step IId to find c Let ngt no and assume TkScklogk for all k in the range no S k lt n In particular when k n3J we have Tn3JS cn3Jlogn3J We must show that Tn S cnlogn Observe Tn 3Tn3J n by the recurrence for T S 3cn 3Jlogn 3J n by the induction hypothesis S 3cn3logn3 n since LxJ S x for all x cnlogn l n cnlogn on n To obtain Tn S cnlogn we need to have cn n S 0 which will be true if c 2 1 Thus as long as c is chosen to satisfy the constraint c 21 the induction step will go through It remains to determine the constant no The base step requires Tno S cno logno This can be viewed as a single constraint on the two parameters c and no which indicates that we have some freedom in choosing them In other words the constraints do not uniquely determine both constants so we must make some arbitrary choice Choosing no 3 is algebraically convenient This yields T3 S 30 whence c 2 T33 Since T3 9 using the recurrence we have the constraint 0 Z 3 Clearly if we choose 0 3 both constraints c 21 and c 2 3 will be satisfied It is important to note that we have not proved anything yet Everything we have done up to this point has been scratch work with the goal of finding appropriate values for c and no It remains to present a complete induction proof ofthe assertion Tn S 3nlogn for all n 2 3 Proof I Since T3 3T33J3 3Tl 3 3 2 3 9 and 33log3 9 the base case reduces to 9 S 9 which is true II Let n gt 3 and assume for all k lt n that Tk S 3klogk Then Tn 3Tn3J n by the recurrence for T S 3 3n3Jlogn3J n by the induction hypothesis letting k n3J S 9n3logn3 n since LxJ S x for all x 3nlogn l n 3nlogn 2n S 3nlogn It now follows that Tn S 3nlogn for all n 2 3 It is a somewhat more difficult exercise to prove by the same technique that Tn Qnlogn and hence Tn nlogn Exercise Determine positive numbers 0 and no such that Tn Z cnlogn for all n 2 no Hint Use the following facts 1 LxJ gt x l and 2 log3 LxJZ log3 x l for x 2 32 With some effort its possible to show that c 14 and no 4 work The next example illustrates one complication that can arise in the substitution method Define Tn by the recurrence 1 n 2TLn2J1 n V ND i Tn We guess that Tn On To prove this guess we attempt to nd positive constants c and no such that Tn S on for all n 2 no As before we proceed by mimicking the induction step Let n gt no and assume for all k in the range no S k lt n that Tk S ck In particular for k n2J we have Tn2JS an2J and thus Tn 2Tn2Jl by the recurrence for Tn S 2cn 2Jl by the induction hypothesis S 2cn 2 1 on l Our goal is to determine 0 so that the induction step is feasible We need to reach the conclusion that Tn S on and to do this we must determine a number 0 such that cnl S on But this inequality is obviously false for all positive c Apparently the induction step cannot be made to work which might lead us to believe that our guess is incorrect Actually Tn On is correct as can be seen by other methods so we take a different approach Our trick is to subtract a lower order term from the right side of the inequality we wish to prove To be precise we seek positive constants c no and b such that Tn S cn b for all n 2 no Observe that this inequality also implies Tn On by a result proved in the handout on asymptotic growth rates It may seem counterintuitive to attempt to prove an inequality which is stronger than the one that failed but notice that this strategy allows us to use a stronger induction hypothesis Again let ngt no and assume for all k in the range no Sklt n that TkS ck b and in particular Tn2JS cn2J b Thus Tn 2Tn2Jl by the recurrence for Tn S 2an2J bl by the induction hypothesis S 2cn2 bl since LxJSx on 2b l Ifwe take b 1 then Tn S cn b as desired For the base case let no 1 We must show Tl S c l l which says cZTll 2 Thus we may set no 1 0 2 and bl Exercise Use induction to prove that Tn S 211 l for all n 2 l whence Tn 0n Exercise Referring to the previous example use the substitution method to show that Tn 901 and therefore Tn n The Recursion Tree Iteration Method The recursion tree method can be used to generate a good guess for an asymptotic bound on a recurrence This guess can then be veri ed by the substitution method Since our guess will be veri ed we can take some liberties in our calculations such as dropping oors and ceilings or restricting the values of n Let us begin with the example T 1 lSnlt3 70 2TLn3Jn 7123 Each node in a recursion tree represents one term in the calculation of Tn obtained by recursively substituting the expression for T into itself We construct a sequence of such trees of increasing depths 0 11 tree 15t tree QM tree TU n n Tn3 Tn3 n3 n3 Tn32 Tn32 Tn32 Tn32 gm tree n rt3 n3 rt32 rt32 rt32 rt32 Tn33 Tn33 Tn33 Tn33 Tn33 Tn33 Tn33 Tn33 By summing the nodes in any one of these trees we obtain an expression for Tn After k iterations of this process we reach a tree in which all bottom level nodes are Tn3k 13 tree n n3 n3 nlt rt32 rt32 rt32 Tn3k Tn3k Tn3k Tmst Tn3k Note that there are 2 nodes at depth 139 each of which has value quot31 for 0 S 139 S k l The sequence of trees terminates when all bottom level nodes are Tl ie when n3k 1 which implies k log3n The number of nodes at this bottom level is therefore 2k 21 53 quot10332 Summing all nodes in the nal recursion tree gives us the following expression for Tn krl Tn22 n3 n1 532T1 10 quot10332 m 1 23 3nl 23k nlog3ltz If we seek an asymptotic upper bound we may drop the negative term to obtain Tn S 3n n1 532 Since log3 2 lt l the first term dominates and so we guess Tn 0n Exercise Prove that this guess is correct using the substitution method It is sometimes possible to push these computations a little further to obtain an asymptotic estimate directly with no simplifying assumptions We call this the iteration method We illustrate on the very same example T 1 1Snlt3 70 2TLn3Jn 7123 Here we do not assume that n is an exact power of 3 and keep the oor Substituting this expression into itself ktimes yields Tnn2TLn3J n 2Ln3J2TLLn3J3J n2Ln3J2ZTLn32j n2Ln3J22Ln32J2T 7132 j3j n2Ln3J22n3ZJ 23T n33 krl 22 rt3 2kTLn3kj 10 The process must terminate when k is chosen so that IS Ln 3k Jlt 3 which implies lSn3klt3 3k 9K3 kSlog3nltkl k log3 nJ krl With this value of k we have TQn3kjl whence Tn22 ill31 2k This expression in 10 essence converts the computation of Tn from a recursive algorithm to an iterative algorithm which is why we call this the iteration method This summation can now be used to obtain asymptotic upper and lower bounds for Tn Tnk12 rt3 2k 10 krl S 22 rt3 21 53 since LxJS x W o krl nZ23 We 0 1 23Y log n 1 23 3nl 23k We S 3n 711 dropping the negative term 0n since log3 2 lt 1 Thus Tn 0n has been proved Note that our proof is rigorous since at no point have we made any simplifying assumptions such as n being an exact power of 3 Therefore there is no need to verify Tn 0n by another method such as substitution In a similar fashion one can show Tn Qn krl Tn22 lit3 2k 3 z 2 n3 1 21 1 since LxJgtx 1 71 krl 1 n 23 22 711 10 10 k Z 22 11 inmgzm replacing the rst sum by 1 Z n 21 53 l 711033 since LxJSx n l 171mg 2 Qn since log3 2 lt 1 We ve shown Tn 901 and since Tn 0n we now have Tn n The iteration method can even be used to nd exact solutions to some recurrences as opposed to the asymptotic solutions we have been satis ed with up to now For example de ne the function Tn by T0 Tl 5 and Tn Tn 2 n for n 2 2 Iterating ktimes we nd Tn nTn 2 nn 2Tn 4 nn 2n 4Tn 6 Eat 2i Tn 2k as H Ho kil n ZZi Tn 2k 10 3 I 2 w Tn 2k kn kk 1 Tn 2k This process must terminate when k is chosen so that either n 2k 0 or 71 2k 1 which is where the recurrence bottoms out39 so to speak This implies 0Sn 2klt2 2kSnlt2k2 ks ltk1 2 kLn2J Thus if k Ln2J we have Tn 2k 5 and therefore the exact solution to the above recurrence is given by Tn Lit2 n Ln2JLn2J 1 5 The asymptotic solution is now readily seen to be Tn nz Exercise De ne Tn by Tl 0 and Tn Tln2Jl for n 2 2 Recall this was example 3 in the induction handout Use the iteration method to show Tn lgnJ for all n whence Tn logn The Master Method This is a method for nding asymptotic solutions to recurrences of the form Tn aTnb fn where a Z l b gt1 and the function f n is asymptotically positive Here Tn b denotes either Tn bl or Tl n b l and it is understood that Tn l for some nite set of initial terms Such a recurrence describes the run time of a 39divide and conquer algorithm which divides a problem of size n into a subproblems each of size n b In this context f n represents the cost of doing the dividing and recombining Master Theorem Let aZl b gt1 fn be asymptotically positive and let Tn be de ned by Tn aTnbfn Then we have three cases 1 If fn 0nl g 395 for some 8 gt 0 then Tn nl g 7 2 If fn nl g then Tn nl g logn 3 If fn Qnl g for some 8 gt 0 and if afnb S cfn for some 0 lt 0 lt1 and for all suf ciently large n then Tn fn 1 57 and the solution is determined by 103MB Remarks In each case we compare f n to the polynomial n which function is of an asymptotically higher order In case 1 n 10mm is polynomially larger than f n and the solution is in the class n In case 3 f n is polynomially larger and an additional regularity condition is met so the solution is f n In case 2 the functions are asymptotically equivalent and the solution is in the class nl g logn which is the same as fnlogn To say that nl gb a is polynomially larger than fn as in 1 means that fn is bounded above by a function which is smaller than nl gba by a polynomial factor namely n5 for some 8 gt 0 Note that the conclusion reached by the master theorem does not change if we replace f n by a function asymptotically equivalent to it For this reason the recurrence may simply be given as Tn aTnb fn Notice also that there is no mention of initial terms It is part of the content of the master theorem that the initial values of the recurrence do not effect it s asymptotic solution

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.