# Recurrence relation using the master theorem $T(n) = 4T(n/2) + n^2 \log n$

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

$T(n) = 4T(n/2) + n^2 \log n$

So: $a=4 ,b=2, f(n)=n^2\log n$ , then $n^{\log_2 4}=n^2$

Now i know that $n^2 \log n$ is larger .

Can I apply the master theorem to this problem?

Thanks.

-
Try the case 2 of the master theorem: en.wikipedia.org/wiki/Master_theorem –  Paresh Feb 24 '13 at 17:15

This recurrence has an explicit solution when $T(0) = 0$ the same way as was done here. Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary digit representation of $n.$ We assume that the logarithm in the recurrence is binary, so that $$T(n) = 4 T(n/2) + \lfloor \log_2 n \rfloor n^2.$$ It is not difficult to see that $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j (\lfloor \log_2 n \rfloor-j) \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} \right)^2 = \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor-j) \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k \right)^2.$$ Now for a lower bound take the case where all binary digits are zero except the leading one. This gives $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor-j) 2^{2 \lfloor \log_2 n \rfloor} \\ = \lfloor \log_2 n \rfloor (\lfloor \log_2 n \rfloor + 1) 2^{2 \lfloor \log_2 n \rfloor} - \frac{1}{2} \lfloor \log_2 n \rfloor (\lfloor \log_2 n \rfloor + 1) 2^{2 \lfloor \log_2 n \rfloor}$$ giving $$T(n)\ge \frac{1}{2} \lfloor \log_2 n \rfloor (\lfloor \log_2 n \rfloor + 1) 2^{2 \lfloor \log_2 n \rfloor}$$ We get an upper bound when all the digits are one, giving $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor-j) \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k \right)^2 = \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor-j) \left( 2^{\lfloor \log_2 n \rfloor +1} - 2^j\right)^2 \\ = \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor-j) \left(2^{2\lfloor \log_2 n \rfloor +2} - 2^{\lfloor \log_2 n \rfloor +2 + j} + 2^{2j} \right) \\ = 2 \lfloor \log_2 n \rfloor (\lfloor \log_2 n \rfloor + 1) 2^{2 \lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor-j) \left(- 2^{\lfloor \log_2 n \rfloor +2 + j} + 2^{2j} \right)$$ With a bit of algebra the remaining sum simplifies to $$- \frac{68}{9} 2^{2\lfloor \log_2 n \rfloor} + 4 \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} + 8\times 2^{\lfloor \log_2 n \rfloor} - \frac{1}{3} \lfloor \log_2 n \rfloor - \frac{4}{9}.$$ giving $$T(n) \le 2 \lfloor \log_2 n \rfloor (\lfloor \log_2 n \rfloor + 1) 2^{2 \lfloor \log_2 n \rfloor}- \frac{68}{9} 2^{2\lfloor \log_2 n \rfloor} + 4 \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} \\ + 8\times 2^{\lfloor \log_2 n \rfloor} - \frac{1}{3} \lfloor \log_2 n \rfloor - \frac{4}{9}.$$ These bounds are actually attained for $n = 2^j$ and $n = 2^{j+1}-1$ and hence cannot be improved.
To conclude we take the leading terms of the two expansions to get $$T(n) \in \Theta\left(\lfloor \log_2 n \rfloor^2 2^{2 \lfloor \log_2 n \rfloor}\right) = \Theta\left((\log_2 n)^2 2^{2 \lfloor \log_2 n \rfloor}\right) = \Theta\left((\log_2 n)^2 n^2\right) = \Theta\left((\log n)^2 n^2\right).$$ The above method yields an algorithm to solve all Master type recurrences exactly when the work term is $(\log n)^p n^q$, with $p$ and $q$ positive integers.