Блог пользователя mkagenius

Автор mkagenius, 14 лет назад, По-английски
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.?
  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
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))
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 ?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      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.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
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).
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
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.
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
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)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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. ?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    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.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
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)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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 "