Introduction to Algorithm 3rd edition, Exercise 4.3-6

Question

4.3-6 Show that the solution to T(n)=2T(n/2 + 17) + n is O(nlgn).

Using substitution method, I tried to solve this question by assuming

T(n/2+17) <= C(n/2+17)lg(n/2+17)

However I can not work it out, any suggestions?

Answer 1

let f(n)=T(n+34) then you get f(n)=T(n+34)=2T(n/2+34)+n+34=2f(n/2)+n+34, try to solve f(n), then you get T(n). In fact, for T(n)=2(n/2+c)+n, with the master theorem, you can ignore the const c.