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.6Day 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 ]