Substitution Method

Good Guesses

T (n) = 2 T ( ë n/2 û ) + n

T (n) = O (n lg n ) is a guess

Show that T (n) = O (n lg n ) £ c n lg n

T (n)  £ c n lg ( n/2 ) + n

= c n ( lg n - lg 2 ) + n

= c n  lg n - cn + n

£ c n lg n  when c  ³ 1 as -c n + n  £ 0 in that case

We must verify the "boundary condition." It is often better to move the boundary condition to other values.

Indeed it is easy to show that we have: T (n) = Q (n lg n ).

Making good guesses is important.

1. Constants don't change things much T (n) = 2 T ( ë n/2 û  + 17 ) + n still has T (n) = Q (n lg n ) .

2. Find loose upper and lower bounds

3. Sometimes must strengthen assumption to get good induction

T (n) = T ( ë n/2 û ) + T (  é n/2 ù ) +  1

T (n) £ c n ® try it

T (n) £ c ë n/2 û + c  é n/2 ù  + 1

£ c n + 1 ® the '1' is a problem, but

T (n) = c n - b, b  ³ 0 constant works

Changing variables:

T (n) = 2 T ( ë Ön û ) + lg n

let m = lg n Û n = 2^m

T (2^m) = 2 T ( 2^m/2 ) + m

let S (m) = T (2^m)

S (m) = 2 S ( m/2 ) + m Þ S (m) = O (m lg m )

          Þ T (n) = O (lg n lg lg n )