Solving square root recurrences

Question

How can I solve that recurrence a square root?

Answer 1

Since you haven't specified the domain on $n$ nor the base case, I made some assumptions about the recurrence. Let $a$ represent the base case for the recurrence such that $$T(n)=\begin{cases} a,&n\leq 1\\ 4T\left(n/2\right)+n^2\sqrt{n},&n>1 \end{cases},$$ where $n\in\mathbb{R}$.

Unfolding the recurrence gives us $$ \begin{align} T(n)&=4T\left(\frac{n}{2}\right) + n^2\sqrt{n}\\ &=4\left(4T\left(\frac{n}{4}\right)+\left(\frac{n}{2}\right)^2\sqrt{\frac{n}{2}}\right)+n^2\sqrt{n}\\ &=4\left(4\left(4T\left(\frac{n}{8}\right)+\left(\frac{n}{4}\right)^2\sqrt{\frac{n}{4}}\right)+\left(\frac{n}{2}\right)^2\sqrt{\frac{n}{2}}\right)+n^2\sqrt{n}\\ &\ldots\\ &=4^{p}T(1)+4^{p-1}f(x_{p-1})+\dots+4^2f(x_2)+4f(x_1)+f(x_0), \end{align} $$ where $p$ represents the number of times that $n$ is halved in order to reach $1$, $f(x)=x^2\sqrt{x}$ represents the constant term of $T(x)$, and $x_k=n/2^k$. In other words, the expanded recurrence will have $p+1$ terms (one for each nested recurrence, plus the constant term). Notice that $f(x_p)\approx 1$ since $p$ represents the number of times that we must recur to get to $1$, and $f(1)=1$. The number of times that $n$ is halved is the solution to $$\frac{n}{2^x}=1\implies n=2^x\implies x=\log_2(n),$$ meaning $p=\left\lceil\log_2(n)\right\rceil$.

Rewriting $T(n)$ as a summation, we get $$ \begin{align} &\;4^pT(1)+\sum^{p-1}_{i=0}4^if(x_i)\\ =&\;4^pT(1)+\sum^{p-1}_{i=0}\left(4^i \left(\frac{n}{2^i}\right)^2\sqrt{\frac{n}{2^i}}\right)\\ =&\;4^pT(1)+\sum^{p-1}_{i=0}4^i \left(\frac{n}{2^i}\right)^{5/2}\\ =&\;4^pT(1)+\sum^{p-1}_{i=0}\frac{2^{2i}n^{5/2}}{2^{5i/2}}\\ =&\;4^pT(1)+n^{5/2}\sum^{p-1}_{i=0}2^{-i/2}.\\ \end{align} $$ Or, alternatively $$T(n)=4^pT(1)+n^{5/2}\sum^{p-1}_{i=0}\left(\frac{\sqrt{2}}{2}\right)^i,$$ which is just a geometric series. So $T(n)$ can be written in closed form as $$T(n)=4^pT(1)+n^{5/2}\left(\frac{2^{1-p/2}-2}{\sqrt{2}-2}\right).$$