Comparing two recurrence relations w.r.t. asymptotic growth
You can sort of get a feel of the asymptotic behavior of a recurrence by flatting out the recurrence into an equivalent problem of the form $A_k = c_1(k) A_{k-1} + c_2(k)$.

First of all, to see that $O(n^2)$ is an extremely loose bound, notice how $T_1(16)$ expands out:
\begin{align*}
T_1(16) &amp;= 4 T_1(4) + 3 \cdot 16 \\
&amp;= 4 (2 T_1(2) + 3 \cdot 4) + 3 \cdot 16 \\
&amp;= 8 + 2 \times (3 \cdot 16)
\end{align*}
Similarly, you'll find that $T_1(256)$ expands out to
\begin{align*}
T_1(256) &amp;= 16 T_1(16) + 3 \cdot 256 \\
&amp;= 16 (8 + 2 \times (3 \cdot 16)) + 3 \cdot 256 \\
&amp;= \frac{256}{2} + 3 \times (3 \cdot 256)
\end{align*}
This strongly suggests that $T_1(2^{2^k}) = 2^{2^{k-1}} + 3k 2^{2^k}$, or $T_1(n) \approx \frac{n}{2} + 3 n\log_2 \log_2 n$. We can show this by first relaxing the domain of the function to those of the form $2^{2^k}$. Since $\sqrt{2^{2^k}} = 2^{2^{k-1}}$, we have
$$
T_1(2^{2^k}) = 2^{2^{k-1}} T_1(2^{2^{k-1}}) + 3 \cdot 2^{2^k}
$$
Let $A_k = T_1(2^{2^k})$, then
\begin{align*}
A_k &amp;= 2^{2^{k-1}} A_{k-1} + 3 \cdot 2^{2^{k}} \\
&amp;= 3 \cdot 2^{2^{k}} + 2^{2^{k-1}}(3 \cdot 2^{2^{k - 1}} + 2^{2^{k - 2}}A_{k-2}) \\
&amp; \cdots \\
&amp;= 2^{2^{k - 1}}A_{0} + 3 \cdot 2^{2^{k}} + 3 \cdot 2^{2^{k}} + \stackrel{k}{\dots} + 3 \cdot 2^{2^{k}}
\end{align*}

which shows that when $n = 2^{2^k}$, then $T_1(n) = \Theta(n\log\log n)$. Suppose we now open $T_1(n)$ over the whole real domain (that is, we relax the domain restriction imposed previously), then it should be easy to show that if $T_1(x) = 1$ whenever $x \in [1, 2]$, then $T_1(n) = \frac{n}{2} + 3n \log_2\log_2 n$ extends uniformly. (Proof: Use the same derivation above, but for some other $p \in [1, 2]$, do the case analysis on $p^{2^k}$ instead)

Therefore, we have $T_1(n) = \Theta(n \log\log n)$ and $T_2(n) = \Theta(n^2 \log n)$. Asymptotically, $T_2$ still dominates $T_1$.