# How to solve recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$

I have tried solve the recurrence $$T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$$ using substitution. Apparently, it is exact for some $$n$$ and the order of the general solution can be found from this exact solution.

By substitution I got the following (not sure if it is correct):

$$T(n) = 5^kT(1) + \sum_{i = 0}^{k}{5^{i}\left(\frac{n}{2^{i}}\right)^{2}\lg^{2}\left(\frac{n}{2^{i}}\right)}$$

I am not sure how to proceed from this. I don't even know if this approach is correct so far. How do I solve this recurrence?

You can use the master theorem. This theorem allows you to solve some recurrences of the form $$T(n) = aT(n/b) + f(n)$$.

You need to compare $$n^{\log_b a}$$ with $$f(n)$$. In you case $$n^{\log_b a} = n^{\log_2 5}$$ and $$f(n)=n^2 \log^2 n$$.

There are different cases depending on how the above functions compare, but I am only going to discuss the one that is relevant to you (you can find more on Wikipedia).

In your case $$f(n) = O(n^{\log_b a - c})$$ for some constant $$c>0$$. To see this pick, e.g., $$c=0.1$$ and substitute to obtain: $$n^2 \log^2 n = O(n^{\log_2 5 -0.1})$$, which is true since $$\log_2 5 - 0.1 > 2$$.

The master theorem then tells you that $$T(n) = \Theta(n^{\log_b a})$$, which in your case is $$T(n) = \Theta(n^{\log_2 5})$$.

• But is this an exact solution? – bingbong Jun 11 '20 at 21:21
• What do you mean by "exact solution"? It is not an equality but since $T(n) \in \Theta(n^{\log_2 5})$ this tells you that there are two constants $c_1$ and $c_2$ with $0 \le c_1 \le c_2$ such that, for every sufficiently large value of $n$, $c_1 n^{\log_2 5} \le T(n) \le c_2 n^{\log_2 5}$. – Steven Jun 11 '20 at 21:21
• By exact solution I mean an equality. But I suppose, this is good enough. Thank you! – bingbong Jun 11 '20 at 21:34
• I am not familiar with the master theorem, could you show how to solve this problem with it in your solution? @Steven – bingbong Jun 11 '20 at 21:34
• I have edited my answer to add mode details. – Steven Jun 11 '20 at 21:42