Facing the problem:
$$f(n) = 4f(n-1) + ({\log_{2}{n}})^{2}$$
How can I find the best approximation of $f(n)$ in the big $O$ notation?
My approach (let's assume $T(0) = 0$)
$$f(n) = 4f(n-1) + ({\log_{2}{n}})^{2} = 4^{n}*f(0) + c * \sum_{i=0}^{n-1} 4^{i}*{\log_{2}^2 (n-i)}$$
What can I conclude from this sum?
Getting
$$f(n) = 4^n\cdot f(0) + \sum_{i=0}^{n-1}{4^i\cdot (\log_2(n-i))^2}$$
is most of the work. Just rewrite the sum as
$$\sum_{i=1}^{n}{4^{n-i}(\log_2{i})^2} < 4^n\sum_{i=1}^{\infty}{\frac{(\log_2{i})^2}{4^i}} = C\cdot 4^n$$
to conclude that $f(n) = O(4^n)$.
If you want an asymptotic formula for $f(n)$, just do the same without the inequality:
$$\sum_{i=1}^{n}{4^{n-i}(\log_2{i})^2} = 4^n\left(\sum_{i=1}^{\infty}{\frac{(\log_2{i})^2}{4^i}} - \sum_{i=n+1}^{\infty}{\frac{(\log_2{i})^2}{4^i}}\right)$$
$$= 4^n\left(C + O\left(\frac{\log^2{n}}{4^n}\right)\right) = C\cdot 4^n + O(\log^2{n}).$$
This gives the formula
$$f(n) = \left(f(0)+C\right)4^n + O\left(\log^2{n}\right)$$