a tighter upper bound? We shall prove that r(n)=o(n2) Assume that t(k)s ck for k<n T(m)=47(n/2)+n <4cn2tn Wrong! We must prove the IH C (n)[ desired -residual cn for no choice of c>o. lose Day 3 Introduction to Algorithms L2.6
Day 3 Introduction to Algorithms L2.6 A tighter upper bound? We shall prove that T(n) = O(n2). Assume that T(k) ≤ ck2 for k < n: ( ) 4 ( ) 4 ( / 2) 2 O n cn n T n T n n = ≤ + = + Wrong! We must prove the I.H. 2 2 ( ) cn cn n ≤ = − − for no choice of c > 0. Lose! [ desired – residual ]
A tighter upper bound! IDEA: Strengthen the inductive hypothesis Subtract a low-order term inductive hypothesis: T(k)<c,k2-ck for k<n T(m)=47(n/2)+n ≤4(c(n/2)2-c2(m/2)+n =cin2-2contn Cin--Con-(Con-n ≤C1n n if c> 2 Pick c, b Day ig enough to handle the initial conditions Introduction to Algorithms 7
Day 3 Introduction to Algorithms L2.7 A tighter upper bound! IDEA: Strengthen the inductive hypothesis. • Subtract a low-order term. Inductive hypothesis: T(k) ≤ c1k2 – c2k for k < n. ( ) 2 4( ( / 2) ( / 2) ( ) 4 ( / 2) 2 2 1 2 2 2 1 2 2 1 2 2 1 c n c n c n c n c n n c n c n n c n c n n T n T n n ≤ − = − − − = − + ≤ − + = + if c2 > 1. Pick c1 big enough to handle the initial conditions
Recursion -tree method A recursion tree models the costs(time)of a recursive execution of an algorithm The recursion tree method is good for generating guesses for the substitution method The recursion -tree method can be unreliable just like any method that uses ellipses(.) The recursion-tree method promotes intuition however Day 3 Introduction to Algorithms L2.8
Day 3 Introduction to Algorithms L2.8 Recursion-tree method • A recursion tree models the costs (time) of a recursive execution of an algorithm. • The recursion tree method is good for generating guesses for the substitution method. • The recursion-tree method can be unreliable, just like any method that uses ellipses (…). • The recursion-tree method promotes intuition, however
Example of recursion tree Solve(m)=70n/4)+7(m/2)+n Day 3 Introduction to Algorithms L2.9
Day 3 Introduction to Algorithms L2.9 Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2:
Example of recursion tree Solve(m)=70n/4)+7(m/2)+ 7(n) duction to algorith L2.10
Day 3 Introduction to Algorithms L2.10 Example of recursion tree T(n) Solve T(n) = T(n/4) + T(n/2) + n2: