Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Yes, because $\log n=o(n^\epsilon)$ for any $\epsilon > 0$. –  Louis Jan 31 '12 at 22:37
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks for the explanation, it helped a lot! –  gprime Feb 2 '12 at 0:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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