Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite 
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!

share|improve this question
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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.