I am trying to solve the following recurrence relation using the master theorem:

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


$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 polynomial 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.

  • $\begingroup$ Yes, because $\log n=o(n^\epsilon)$ for any $\epsilon > 0$. $\endgroup$
    – Louis
    Jan 31 '12 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)$.

  • $\begingroup$ Thanks for the explanation, it helped a lot! $\endgroup$
    – gprime
    Feb 2 '12 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} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.