5
$\begingroup$

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.

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

2 Answers 2

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the explanation, it helped a lot! $\endgroup$
    – gprime
    Commented Feb 2, 2012 at 0:56
-1
$\begingroup$

$$ 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} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .