# $T(n) = 4T(n/2) + \theta(n\log{n})$ using Master Theorem

I am trying to solve the following recurrence relation using the Master Theorem:

$$T(n) = 4T(n/2) + \theta(n\log{n})$$

So:

$$a = 4$$, $$b = 2$$, and $$f(n) = n\log{n}$$

So we are comparing:

$$n^{\log_b{a}}$$ with $$n\log{n}$$

$$n^{\log_2{4}} = n^2$$ so we are comparing $$n^2$$ with $$n\log{n}$$

Now I know that $$n^2$$ is larger but is it polynomially larger than $$n\log{n}$$?

Can I apply the Master Theorem to this problem? If so, which case applies to this problem?

Any help would be appreciated.

• Yes, because $\log n=o(n^\epsilon)$ for any $\epsilon > 0$. Commented Jan 31, 2012 at 22:37

Your recurrence relation falls into Case 1: $$f(n) = n \log n$$ is $$O(n^{\log_{b}{a}-\epsilon}) = O(n^{2-\epsilon})$$.

To show why this is Case 1, as Louis says, logarithmic functions ($$\log n$$) are asymptotically bounded by polynomial functions ($$n^a$$, where $$a > 0$$). This can be shown by taking the limit: $$\lim_{n \to \infty} \frac{\log n}{n^a} = 0$$ through L’Hôpital’s rule. In particular, $$\log n \in O(n^{1-\epsilon})$$ for small $$\epsilon$$. (We can go even further and say that $$\log n \in o(n^{1-\epsilon})$$.)

Then by multiplying both sides by $$n$$, (an allowed operation in big-O notation), $$n \log n \in O(n^{2-\epsilon})$$.

Therefore by the Master Theorem, $$T(n)$$ is $$\Theta(n^2)$$.

• Thanks for the explanation, it helped a lot! Commented Feb 2, 2012 at 0:56

$$T(n)=4T\left(\frac{n}{2}\right)+\theta(n\log n)$$ Step 1: $$T(n)=4T\left(\frac{n}{2}\right)+\theta(n\log n) \iff T(n)=aT\left(\frac{n}{b}\right)+\theta(f(n))$$ where $$a=4,b=2,f(n)=n\log n$$. Whenever we are solving by using the master method, remove the polynomial, logarithmic, exponential part from the equation. Therefore , $$f(n)=n$$.
Step 2: $$n^{\log_ba} = n^{\log_2 4} =n^2$$.
Step 3: Compare $$n_2$$ v/s $$f(n)$$, i.e. $$n^2$$ v/s $$n$$. Since $$n^2$$ is greater than $$n$$ so, Case 1 : if $$n^{\log_b a} > f(n)$$, then $$T(n)= θ(n^{\log_ba}) =θ(n^2)$$ with $$\begin{split} \epsilon &= \text{exponential power of }n^{\log_ba} - \text{ exponential power of }f(n)=n^2-n \\ &=\text{power of }n^2 =2-(\text{power of }n =1) = 2-1 =1 \end{split}$$