Recurrence with a function of n times T()

Question

The master method works well on problems like $T(n)=kT(an)+cn$, but it does not handle problems like $$T(n)=n^{\frac{1}{3}}T(n^{\frac{2}{3}})+n^2$$ With the number of branches for each partition is a function of $n$. I wonder if there's a good solution to this kind of problems, I have no idea how to solve this, any help is appreciated!

Answer 1

You can use the more elementary method in which you expand the recurrence: \begin{align} T(n) &= n^2 + n^{1/3} T(n^{2/3}) \\ &= n^2 + n^{5/3} + n^{5/9} T(n^{4/9}) \\ &= n^2 + n^{5/3} + n^{10/9} + n^{19/27} T(n^{8/27}) \\ &= \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>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.