Question

Solve recurrence relation with repeated substitution (again ugh)

Answer 1

(√n)T((√n)+n

Answer 2

I did get the answer (n1/2∗n1/22∗...∗n1/2k)T(n1/2k)+(n1/2k−1+...+n1/2+n) but I don't know how to simplify so...?

Answer 3

Is that supposed to be
\[T(n)=\sqrt nT(\sqrt n)+n~~?\]

Answer 4

If so, recursive substitution gives
\[\begin{align*}
T(n)&=\sqrt n\,T(\sqrt n)+n\\[1ex]
&=\sqrt n\left(\sqrt[4]n\,T(\sqrt[4]n)+\sqrt n\right)+n\\[1ex]
&=\sqrt[4]{n^3}\,T(\sqrt[4]n)+2n\\[1ex]
&=\sqrt[4]{n^3}\left(\sqrt[8]n\,T(\sqrt[8]n)+\sqrt[4]n\right)+2n\\[1ex]
&=\sqrt[8]{n^7}\,T(\sqrt[8]n)+3n\\[1ex]
&=\sqrt[8]{n^7}\left(\sqrt[16]n\,T(\sqrt[16]n)+\sqrt[8]n\right)+3n\\[1ex]
&=\sqrt[16]{n^{15}}\,T(\sqrt[16]n)+4n\\[1ex]
&~~\vdots\\[1ex]
&=\sqrt[2^k]{n^{2^k-1}}\,T\left(\sqrt[2^k]n\right)+kn
\end{align*}\]

Answer 5

@HolsterEmission thank you! Can you check this next part?
assume: \[\sqrt[2^{k}]{n} =2 \] so \[n=2^{2^{k}}\]
so \[k=\log_{2} \log_{2} n\] so I've put the original equation into the form \[=\frac{ n }{ 2 }T(2)+n \log_{2} \log_{2} n\]
Is that right or have I made up some new math?

Answer 6

Yup, looks good to me!

Answer 7

thanks again :)