# Recurrence Relation - $T(n) = 4T(n/2) + n^2\log n$ - Solve using the tree method

We're given the function $T: \mathbb{N} \rightarrow \mathbb{R}$ which takes a constant value for $n \leq 4$ and for all other $n \in \mathbb{N}$ it is through the following recurrence relation defined: $T(n) = 4T(n/2) + n^2\log(n)$.

I need to provide a function $g$, so that $T \in \Theta(g)$.

After drawing my tree, I got to the general equation which says that for $T(n/2^i)$ we'll be at level $i$ and we'll have habe $4^i$ nodes with the sum of the level being $n^2\log(n/2^i)$. So far am I correct?

The next problem I had was that I wasn't sure of my base case, so I assumed $T(1) = 1$, but now thinking about it, it probably has to do with the very first sentence saying that the function takes a constant for an $n \leq 4$, but I'm not sure how to get the base case from that.

Assuming $T(1) = 1$, I went ahead and calculated my $i$ value for the base case: $1 = n/2^i \Rightarrow i = \log_2n$. So out of that, I started summing back up, so I had:

$$T(n) = n^{\log_24} + \sum_{i=0}^{\log n-1}n^2\log\Big(\frac{n}{2^i}\Big)$$ after some simplifying I got to $$n^2 + n^2\Bigg(\sum_{i=0}^{\log n-1}\log n - \sum_{i=0}^{\log n-1}\log 2^i (= i?)\Bigg) \quad$$

Eventually I used some sigma notation rules (first sigma was just a constant being summed up $\log n$ times, second one was the gauß sum up to $\log n - 1$, and got to:

$$n^2 + n^2\Bigg(\frac{\log n^2}{2}\Bigg)$$

I am pretty sure that I made a mistake somewhere, but in case I didn't, I then assumed that $T \in \Theta\big(n^2 ((\log(n))^2\big)$

Any input would be appreciate on how to go about this or where I made a mistake... I've been stuck with this equation for over $5$ hours and can't seem to get it right. Everytime I go at it, I get a different answer.

Thanks!

Your solution is correct. A problem of size $n$ takes $O(n^2\log n)$ time, plus four subproblems that take $\left(\frac n2\right)^2\log\frac n2$, which sum to $O(n^2\log n)$ time. There are $\log n$ levels in the recursion tree, and hence the overall runtime is $O((n\log n)^2)$. Indeed, if we assume that $T(n) \leqslant C(n\log n)^2$ for some constant $C$, then $$T(2n) = 4T(n) + (2n)^2\log 2n \leqslant 4C(n\log n)^2 + 8n^2\log n\leqslant C'(n\log n)^2$$ for a constant $C'$, so we conclude by induction that $T(n)\in O((n\log n)^2)$.