Help with a recurrence relation

Question

I have been battling with the following:

$$T\left(n\right)=3T\left(\frac{n}{2}\right)+n\log(n)$$

I have tried expanding it but the term $n\log(n)$ gets very messy. What is the approach for solving this recurrence?

Substitute $t = 2$ then $t = 1$ – Varun Iyer Sep 04 '14 at 23:39 — Varun Iyer, Sep 04 '14 at 23:39
What is $n\log n - 3\frac{n}{2}\log\frac{n}{2}$? – achille hui Sep 04 '14 at 23:52 — achille hui, Sep 04 '14 at 23:52

score 4 · Accepted Answer · answered Sep 05 '14 at 00:48

If you have encountered the Master Theorem, then this is an extremely easy solution. Since this is of the form:

$ T(n) = aT(\frac{n}{b}) + f(n) $

$a = 3$, $b = 2$, and $f(n) = n\log n$. $f(n) = O( n^{\log_2 3} - \epsilon)$, which means case 1 applies and $T(n) = O(n^{\log_2 3})$

score 0 · Answer 2 · answered Sep 05 '14 at 00:29

0

$T(n)=O(n^{\log_2 3})$

To see why, first consider what happens if the $n\log n$ term is missing. Then we get $T(n)=O(n^{\log_2 3})$. Now observe that $n^{\log_2 3}>>n\log n$ asymptotically, so introducing the $n\log n$ doesn't change the asymptotics.

answered Sep 05 '14 at 00:29

pre-kidney

30,223

Help with a recurrence relation

2 Answers2