Recurrence with a function of n times T()
You can use the more elementary method in which you expand the recurrence:
\begin{align}
T(n) &amp;= n^2 + n^{1/3} T(n^{2/3}) \\ &amp;= n^2 + n^{5/3} + n^{5/9} T(n^{4/9}) \\ &amp;= n^2 + n^{5/3} + n^{10/9} + n^{19/27} T(n^{8/27}) \\ &amp;= \cdots
\end{align}
This suggests that $T(n) = O(n^2)$. Indeed, let us try to prove by induction that $T(n) \leq Cn^2$:
$$
T(n) \leq n^2 + n^{1/3} \cdot Cn^{4/3} = n^2 \left(1 + \frac{C}{n^{1/3}}\right),
$$
which will be at most $Cn^2$ for any $C&gt;1$ and large enough $n$ (depending on $C$).
Indeed, defining $S(n) = T(n) - n^2$, we have
$$
S(n) = n^{5/3} + n^{1/3}S(n^{2/3}),
$$
and so the same argument shows that $S(n) = O(n^{5/3})$ and so $T(n) = n^2 + O(n^{5/3})$. In the same way, we can get $T(n) = n^2 + n^{5/3} + O(n^{10/9})$, and so on.