# Tag Info

2

Yes, you can define $T'(n) = 2 T'(\frac{n}{2}) + \Theta(n \log n)$, notice that $T(n) \le T'(n)$, and use the master theorem on $T'$ to obtain an upper bound of $O(n \log^2 n)$ to $T$. Since for $n \ge 2$, $\frac{2+\log n}{1+\log n} \le \frac{3}{2}$ you can get a better upper bound by comparing $T$ to T'' = \begin{cases}\frac{3}{2}T''(\frac{n}{2}) + \...

Only top voted, non community-wiki answers of a minimum length are eligible