Example of substitution T(n)=47(n/2)+n ≤4c(n/2)3+n =(c/2n3+n cn3-((c/2)n3-n+ desired-residual <Cn3← desire whenever(c/2)n3-n20, for example fc≥2andn≥1 residue Day 3 Introduction to Algorithms L24Day 3 Introduction to Algorithms L2.4 Example of substitution 3 3 3 3 3 (( / 2) ) ( / 2) 4 ( / 2) ( ) 4 ( / 2) cn cn c n n c n n c n n T n T n n ≤ = − − = + ≤ + = + desired – residual whenever (c/2)n3 – n ≥ 0, for example, if c ≥ 2 and n ≥ 1. desired residual