Asymptotic Efficiency of RecurrencesRecurrencesThe Substitution MethodSolve T(n)=2T(n/2)+nBoundary (base) ConditionSubtletiesAvoiding PitfallFind bound, ceiling, floor, lower term– domain transformationChanging VariablesThe Recursion-tree MethodRecursion Tree for T(n)=3T(n/4)+(n2)Solution to T(n)=3T(n/4)+(n2)Prove the above GuessOne more exampleRecursion Tree of T(n)=T(n/3)+ T(2n/3)+O(n)Master Method/TheoremImplications of Master TheoremApplication of Master TheoremSlide 19Exception to Master TheoremWhere Are the GapsProof of Master TheoremRecursion tree for T(n)=aT(n/b)+f(n)Proof of Master Theorem (cont.)Proof of Lemma 4.3Proof of Lemma 4.3(cont.)Slide 27Slide 28Proof of Lemma 4.4 (cont.)Floors and CeilingsUpper bound of proof for T(n)=aT(n/b)+f(n)Recursion tree of T(n)=aT(n/b)+f(n)The proof of upper bound for ceilingThe simple format of master theoremSummary1Asymptotic Efficiency of Recurrences•Find the asymptotic bounds of recursive equations.–Substitution method•domain transformation•Changing variable–Recursive tree method–Master method (master theorem)•Provides bounds for: T(n) = aT(n/b)+f(n) where –a  1 (the number of subproblems).–b>1, (n/b is the size of each subproblem).–f(n) is a given function.2Recurrences•MERGE-SORT–Contains details:•T(n) = (1) if n=1 T(n/2)+ T(n/2)+ (n) if n>1•Ignore details, T(n) = 2T(n/2)+ (n). –T(n) = (1) if n=1 2T(n/2)+ (n) if n>13The Substitution Method•Two steps:1. Guess the form of the solution.•By experience, and creativity.•By some heuristics.–If a recurrence is similar to one you have seen before.»T(n)=2T(n/2+17)+n, similar to T(n)=2T(n/2)+n, , guess O(nlg n).–Prove loose upper and lower bounds on the recurrence and then reduce the range of uncertainty.»For T(n)=2T(n/2)+n, prove lower bound T(n)= (n), and prove upper bound T(n)= O(n2), then guess the tight bound is T(n)=O(nlg n).•By recursion tree.2. Use mathematical induction to find the constants and show that the solution works.4Solve T(n)=2T(n/2)+n•Guess the solution: T(n)=O(nlg n),– i.e., T(n) cnlg n for some c.•Prove the solution by induction: –Suppose this bound holds for n/2, i.e.,•T(n/2) cn/2 lg (n/2).–T(n)  2(cn/2 lg (n/2))+n•  cn lg (n/2))+n• = cn lg n - cn lg 2 +n • = cn lg n - cn +n•  cn lg n (as long as c1)Question: Is the above proof complete? Why?5Boundary (base) Condition •In fact, T(n) =1 if n=1, i.e., T(1)=1.•However, cnlg n =c1lg 1 = 0, which is odd with T(1)=1.•Take advantage of asymptotic notation: it is required T(n) cnlg n hold for n n0 where n0 is a constant of our choosing.•Select n0 =2, thus, n=2 and n=3 as our induction bases. It turns out any c  2 suffices for base cases of n=2 and n=3 to hold.6Subtleties•Guess is correct, but induction proof not work.•Problem is that inductive assumption not strong enough.•Solution: revise the guess by subtracting a lower-order term.•Example: T(n)=T(n/2)+T(n/2)+1.–Guess T(n)=O(n), i.e., T(n)  cn for some c. –However, T(n)  c n/2+c n/2+1 =cn+1, which does not imply T(n)  cn for any c.–Attempting T(n)=O(n2) will work, but overkill.–New guess T(n)  cn – b will work as long as b  1.–(Prove it in an exact way).7Avoiding Pitfall•It is easy to guess T(n)=O(n) (i.e., T(n)  cn) for T(n)=2T(n/2)+n.•And wrongly prove: –T(n)  2(c n/2)+n •  cn+n• =O(n).  wrongly !!!!•Problem is that it does not prove the exact form of T(n)  cn.8Find bound, ceiling, floor, lower term– domain transformation•Find the bound: T(n)=2T(n/2)+n (O(nlogn))•How about T(n)=2T(n/2)+n ?•How about T(n)=2T(n/2)+n ?–T(n)2T(n/2+1)+n–Domain transformation•Set S(n)=T(n+a) and assume S(n)  2S(n/2)+O(n) (so S(n)=O(nlogn))•S(n)  2S(n/2)+O(n) T(n+a)  2T(n/2+a)+O(n)•T(n)2T(n/2+1)+n  T(n+a)  2T((n+a)/2+1)+n+a•Thus, set n/2+a=(n+a)/2+1, get a=2.•so T(n)=S(n-2)=O((n-2)log(n-2)) = O(nlogn).•How about T(n)=2T(n/2+19)+n ? –Set S(n)=T(n+a) and get a=38.•As a result, ceiling, floor, and lower terms will not affect. –Moreover, the master theorem also provides proof for this.9Changing Variables•Suppose T(n)=2T(n)+lg n.•Rename m=lg n. so T(2m)=2T(2m/2)+m.•Domain transformation:– S(m)=T(2m), so S(m)=2S(m/2)+m.–Which is similar to T(n)=2T(n/2)+n.–So the solution is S(m)=O(m lg m). –Changing back to T(n) from S(m), the solution is T(n) =T(2m)=S(m)=O(m lg m)=O(lg n lg lg n).10The Recursion-tree Method•Idea:–Each node represents the cost of a single subproblem.–Sum up the costs with each level to get level cost.–Sum up all the level costs to get total cost.•Particularly suitable for divide-and-conquer recurrence.•Best used to generate a good guess, tolerating “sloppiness”.•If trying carefully to draw the recursion-tree and compute cost, then used as direct proof.11Recursion Tree for T(n)=3T( n/4)+(n2)T(n)(a)cn2T(n/4)T(n/4) T(n/4)(b)cn2c(n/4)2c(n/4)2c(n/4)2T(n/16) T(n/16) T(n/16)T(n/16)T(n/16)T(n/16)T(n/16) T(n/16) T(n/16)(c)cn2c(n/4)2c(n/4)2c(n/4)2c(n/16)2c(n/16)2c(n/16)2c(n/16)2c(n/16)2c(n/16)2c(n/16)2c(n/16)2c(n/16)2cn2(3/16)cn2(3/16)2cn2T(1)T(1) T(1)T(1) T(1)T(1)(nlog 43)3log4n= nlog 43Total O(n2)log 4n(d)12Solution to T(n)=3T(n/4)+(n2)•The height is log 4n, •#leaf nodes = 3log 4n= nlog 43. Leaf node cost: T(1).•Total cost T(n)=cn2+(3/16) cn2+(3/16)2 cn2+  +(3/16)log 4n-1 cn2+ (nlog 43) =(1+3/16+(3/16)2+  +(3/16)log 4n-1) cn2 + (nlog 43) <(1+3/16+(3/16)2+  +(3/16)m+ ) cn2 + (nlog 43) =(1/(1-3/16)) cn2 + (nlog 43) =16/13cn2 + (nlog 43) =O(n2).13Prove the above Guess•T(n)=3T(n/4)+(n2) =O(n2).•Show T(n) dn2 for some d.•T(n) 3(d (n/4)2) +cn2 3(d (n/4)2) +cn2 =3/16(dn2) +cn2  dn2, as long as d(16/13)c.14One more example•T(n)=T(n/3)+ T(2n/3)+O(n).•Construct its recursive tree (Figure 4.2, page 71).•T(n)=O(cnlg3/2n) = O(nlg n).•Prove T(n)  dnlg n.15Recursion Tree of T(n)=T(n/3)+ T(2n/3)+O(n)16Master Method/Theorem•Theorem 4.1 (page 73)–for T(n) = aT(n/b)+f(n), n/b may be n/b or n/b. –where a  1, b>1 are positive integers, f(n)