# $T(n) = 2T(n/2) + O(n\log^2{n}\log\log{n})$

This always comes up.

Without loss of generality, let $n=2^k$ so $k=\log{n}$.

Then:

\begin{align}
T(2^k)
&= 2T(2^{k-1}) + O(2^k\log^2{(2^k)}\log\log{2^k})\\
&= 2T(2^{k-1}) + O(2^k k^2\log{k})\\
&= 2\left(2T(2^{k-2}) + O\left(2^{k-1} {(k-1)}^2\log{(k-1)}\right)\right) + O(2^k k^2\log{k})\\
% Note: Does not fit
% &= 2\left(2\left(2T(2^{k-3}) + O\left(2^{k-2} {(k-2)}^2\log{(k-2)}\right)\right) + O\left(2^{k-1} {(k-1)}^2\log{(k-1)}\right)\right) + O(2^k k^2\log{k})\\
&= \dots\\
&= 2^k O(1) + \sum_{i=0}^k O\left(2^{k} {i}^2\log{i}\right)\\
&= O(2^k) + \sum_{i=1}^k O\left(2^{k} {i}^2\log{i}\right)\\
&\le O(2^k) + k \cdot O\left(2^{k} {k}^2\log{k}\right)\\
&\le O(2^k) + O\left(2^{k} {k}^3\log{k}\right)\\
&=O(n) + O(n\log^3{n}\log{\log{n}})
\end{align}