Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

mkagenius's blog

Find the time complexity in O-notation for the following recurrence relations using Master method.
By mkagenius, 16 years ago, In English
T(n) = 2*T(n/2) + n*log(n) 

I tried to solve it using master method but it doesn't seem to fit any of the three cases.
Am I correct.?
  • Vote: I like it
  • -17
  • Vote: I do not like it

16 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it
I am not sure what you are asking, but if you want the complexity then I believe it is O(log(n) * n * log(n))
→ Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Did u use master method to solve it ?

    Because when I tried to follow Cormen , I was not able to fit it in any of the given cases ?
    → Reply
    • 16 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it
      Cormen clearly states that the method does not cover all possible cases. Another farfetched example would be something like T(n) = T(n/2) + n2*sin(n), which doesn't fit in any category either.
      → Reply
16 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
Just substituting a few times (which appears to be the simplest method) gives
T(n) = 2*T(n/2) + n*log(n)
T(n) = 4*T(n/4) + n*log(n/2) + n*log(n)
T(n) = 8*T(n/8) + n*log(n/4) + n*log(n/2) + n*log(n)
...
So we can see the sum is of order n*log2(n).
→ Reply
16 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it
If you asked about master theorem, it can be sovled using it. And you can find this special case with f(n) = Θ(nlogbalogkn), k≥0, (which is nothing else than generalized case 2 of the theorem) in Cormen (at least, second edition) in problems after the chapter about proof of the master theorem.
→ Reply
16 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it
Reference: Introduction to Algorithm 2nd Edition. Section 4.3 Master Theorem.
The very question has been explained. Its mentioned that:
"The master method does not apply to the recurrence
T(n) = 2T(n/2) + n lg n,
even though it has the proper form: a = 2, b = 2, f(n) = n lg n, and . It might seem that case 3 should apply, since f(n) = n lg n is asymptotically larger than . The problem is that it is not polynomially larger. Consequently, the recurrence falls into the gap between case 2 and case 3 of master theorem."

The recurrence relation is n*(log 2n)
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Thanks for the reply.

As, porsh  and Jacob says , this falls in the gap between case 2 and 3.
I also thought the same.
But Igel_Sk says, it falls in the category of generic case 2.

So , If we go by Igel_Sk , the gap between case 2 and case 3 , is dependent on k.  

Is this master method some kind "standard" thing  , that it has 3 cases only ?
Because when I saw the generic one , I thought every recurrence relation can be manipulated in some way or another and weaved into the master method.

So, If I were asked , use master method to solve this ?
Should i tell that it falls in between case 2 and case 3 or should I tell that it falls in generic case 2. ?
→ Reply
  • 16 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it
    Wikipedia says it falls in generic case 2 (http://en.wikipedia.org/wiki/Master_theorem), Cormen says it doesn't, but gives this case in problems as an addition.

    And the assumption that the gap between case 2 and case 3 is dependent on k isn't correct if I have understood you properly. The generalisation I mentioned only applies to cases when f(n) = Θ(nlogbalogkn) and doesn't cover other variants of f(n) being not asymptotically equal to nlogba  and neither polynomially larger nor polynomially smaller.
    → Reply
16 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it
I believe this is covered by Exercise 4.6-2 in Cormen. It generalizes case 2 of the master theorem. Indeed, the answer is T(n) = Θ(n lg2n)
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Is Master theorem  really a theorem or some kind of hack to help ourselves ?

(Or are every theorem in Math a kind of hack to help ourselves ? )

BTW , whose invention is this theorem ?
I tried to find out but could not get better than this "master theorem is popularised by CLRS "

→ Reply