4
$\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 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.

  • 0
    Yes, because $\log n=o(n^\epsilon)$ for any \epsilon > 0.2012-01-31

2 Answers 2

3

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

  • 0
    Thanks for the explanation, it helped a lot!2012-02-02