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 7Day 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