# Big-Oh Induction?

T(1) = 5
T(n) = 2*T(n/2) + 4*n, n>=2
Prove by induction:
T(n) <= 5(n*log(n)), for all n>=32


As a note, log(n) is referring to log base 2.

I'm good with induction where it's non-recursive, but I have little idea where to go from here.

Here's the beginnings of an idea I had:

T(n) = 2*T(n/2) + 4n
= 2*(2*T(n/4)+4n) + 4n
= 4*T(n/4)+12n
= 2*(2*(2*T(n/8)+4n) + 4n) + 4n
= 8*T(n/8)+28n
!?!??!?!


Help, please? Or point me to a resource where I can learn how to do this? Thanks!

-
 This should be in a FAQ. A lot of Master theorem type recurrences can be solved exactly. While this computes more information than what is required for the asymptotics I believe it does add to the understanding of what exactly is going on with these recurrences. There is one example here and another one here and here. – Marko Riedel Feb 13 at 21:42