3
$\begingroup$

Sorry if this question has been asked before, but I am trying to figure this out. I am using the CLRS text, Introduction to Algorithms. In the Recurrences chapter, in the Master Theorem section, the following example is given with the solution:

$$T(n) = 3T\left(\frac{n}4\right) + n\log n $$

Here,

$$ a = 3, b =4, f(n) = n\log n $$

Using the Master method, it says

$$f(n) = \Omega(n^{\log_4 3 + \epsilon}) $$

I don't understand how $f(n)$ was "assumed" to have this lower bound ($\Omega$). I would be extremely greatful to anyone who points out to me why this is so.

If more details are needed to understand the problem, please let me know. I will add more details to this question.

TIA,

Jake Clawson

EDIT: I thank all those who have responded below. I have replied to each below individually. But my question still stands. The book directly goes on to say that $f(n)$ is $\Omega$. I don't understand this and this is the key to applying the Master Theorem because once $f(n)$ is known that we know which case to apply.

  • 1
    Shouldn't your last displayed equation be about $T(n)$ rather than $f(n)$?2012-02-12
  • 0
    Does the text have a proof of Master's theorem?2012-02-12
  • 0
    @HenningMakholm: $f(n)$ is correct. $T(n)$ for this problem is found out to be (in the solution for this example) as being $\Theta(n\lg n)$2012-02-14
  • 0
    @Aryabhata: Yes the text does have a proof for the Master's theorem. But the text says that the proof (or understanding thereof) is not need to apply the Master Theorem in this case.2012-02-14
  • 0
    @JakeClawson: I have added an answer. Let me know if that helps.2012-02-14

4 Answers 4