Solving the recurrence relation $T(n) = n^{1/2} T(n^{1/2}) + n^{1/2}$ using the back substitution method?

29 Views Asked by At

This is as far as I could proceed :

Let $n = 2^m$, so $m = \log n$

$T(n) = n^{1/2} T(n^{1/2}) + n^{1/2}\implies T(2^m)= 2^{m/2} T(2^{m/2})+ 2^{m/2}$

Let $T(2^m) = S(m)$,

$S(m)= \frac{m}{2}S\left( \frac{m}{2}\right)+ \frac{m}{2}\tag{1}$

$S\left( \frac{m}{2}\right)= \frac{m}{4}S\left( \frac{m}{4}\right)+ \frac{m}{4}\tag{2}$

$S\left( \frac{m}{4}\right)=\frac{m}{8}S\left( \frac{m}{8}\right)+ \frac{m}{8}\tag{3}$

After which I'm probably supposed to substitute $(2)$ in $(1)$ and $(3)$ in its result and then finally get an expression for $k$ and get the result. But I can't seem to proceed further.I found the question over the internet and no base case was given, may be we could consider $T(2) = 2$.

1

There are 1 best solutions below

0
On

Hint suppose $m = 2^k$: $$S(m) = \frac{m}{2}S\left(\frac{m}{2}\right)+\frac{m}{2}$$ $$S(m) = \frac{m}{2}\left(\frac{m}{4}S\left(\frac{m}{4}\right) + \frac{m}{4}\right)+\frac{m}{2}$$ $$S(m) = \frac{m^2}{2\times2^2}S\left(\frac{m}{2^2}\right) + \frac{m^2}{2\times2^2}+\frac{m}{2}$$ $$S(m) = \frac{m^2}{2\times2^2}\left(\frac{m}{2^3}S\left(\frac{m}{2^3}\right) + \frac{m}{2^3}\right) + \frac{m^2}{2\times2^2}+\frac{m}{2}$$ $$S(m) = \frac{m^3}{2\times2^2\times2^3}S\left(\frac{m}{2^3}\right) + \frac{m^3}{2\times2^2\times2^3} + \frac{m^2}{2\times2^2}+\frac{m}{2}$$

Hence, you can find: $$S(m) = \sum_{i=1}^k\frac{m^i}{2^{\frac{i(i+1)}{2}}}$$

Notice that $m = \log(n)$ and $k = \log(\log(n))$