TITLE: Using the substitution method on $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$
QUESTION [0 upvotes]: My task at hand is to find a tight asymptotic upper bound for the recurrence $p(n)=\sqrt{n}p(\sqrt{n})+\sqrt{n}$. My initial idea has been to substitute $m=\lg n$ and define a new recurrence $s(m)=p(2^m)=m/2s(m/2)+m/2$.
This method was described in my book CLRS, and this is where i run into some trouble. I know how to use the substitution method on this recurrence, but i have no idea on how to place my intial guess. I then tried to analyse the recursion tree. We see that on the first layer we have $1$ node with cost $m/2$, on the second layer we have $m/2$ nodes with a cost of $m/2$ giving us a layer cost of $m^2/4$. in general it seems that the total cost of a layer is $m/2^l\cdot\frac{m}{2}\frac{m^2}{4}\cdot...\cdot\frac{m^l}{2^l}$. This seems incorrect, and even if it is correct i am not sure where to go from here. It looks like the cost peaks around some point, and then becomes extremely small. What i guess i need help to, is placing a good guess on an upper bound for $s(m)$

REPLY [0 votes]: You have got
$$s(2n)=ns(n)+n$$
$$=n(\frac{n}{2}s(\frac{n}{2})+\frac{n}{2})+n=\frac{n^2}{2}s(\frac{n}{2})+n+\frac{n^2}{2}$$
$$=\frac{n^2}{2}(\frac{n}{4}s(\frac{n}{4})+\frac{n}{4})+n+\frac{n^2}{2}=\frac{n^3}{2^{1+2}}s(\frac{n}{2^2})+n+\frac{n^2}{2}+\frac{n^3}{2^{1+2}}$$
This pattern continues giving
$$s(2n)=\lim_{x\to\infty}\frac{n^x}{2^{0+1+...+(x-1)}}s(\frac{n}{2^x})+ \sum_{k=0}^\infty \frac{n^{k+1}}{2^{0+1+...+k}}$$
$$=\lim_{x\to\infty}\frac{n^x}{2^{0.5x(x-1)}}s(\frac{n}{2^x})+ \sum_{k=0}^\infty \frac{n^{k+1}}{2^{0.5k(k+1)}}$$
As $s(0)=0$ and $2^{0.5x(x-1)}>>n^x$ the limit is equal to zero. So
$$s(2n)=p(4^n)=\sum_{k=0}^\infty \frac{n^{k+1}}{2^{0.5k(k+1)}}=n+\frac{n^2}{2}+\frac{n^3}{2^{1+2}}+\frac{n^4}{2^{1+2+3}}+...$$
and as this sum is bounded above by $e^x$ because $2^{0.5x(x-1)}$ is much greater than $x!$ for large $x$. So we have
$$p(4^n) \lt e^n \Rightarrow p(n) \lt e^{\log_4{(n)}}$$
$$\therefore p(n)\lt n^\frac{1}{2\ln{2}}$$
{"set_name": "stack_exchange", "score": 0, "question_id": 3115629}