How to solve this recurrence using back substitution: $T(n)=T(n^{1/2})+n$ where T(2)=1

Question

I am trying to solve this recurrence using back substitution.

$$T(n)=T(n^{1/2})+n$$ where T(2)=1

I solved it and got the kth term as follows:

$$T(n)=T(n^{1/2^k})+(n)^{1/2}+(n)^{1/2^2}+(n)^{1/2^3}+....(n)1/{2^{{k-1}}}+n$$

But i don't have any idea how to deal with this series.Please give me some idea to solve this series.

score 1 · Accepted Answer · answered Jul 27 '13 at 13:55

1

Since your sequence is defined only for $n=2^{2^k}$, $k\ge 0$, it seems useful to rewrite it as

$$S(k):=T(2^{2^k}),\quad k\ge 0.$$ Then you are able to write it as $$S(k+1) = S(k) + 2^{2^{k+1}}, \quad S(0) = 1.$$ It would give $$S(k) = -1+\sum_{s=0}^k 2^{2^s}.$$

answered Jul 27 '13 at 13:55

TZakrevskiy

22,980

Hence $S(k)\sim2^{2^k}$. – Did Jul 27 '13 at 13:59
Pls explain a little bit more! – Coffee_lover Jul 27 '13 at 13:59
what abt $$(n)^{1/2}+(n)^{1/2^2}+(n)^{1/2^3}+....(n)^{1/2^{{k−1}}}+n$$ – Coffee_lover Jul 27 '13 at 14:03
@Did indeed it is. Though I don't really see a closed form for $S(k)$ other than the direct sum. – TZakrevskiy Jul 27 '13 at 14:51
1

@Coffee_lover Your expression is the same as mine up to a change $2^{2^k}\to n$. Please specify where you need more clarifications, I don't see any hard points there. – TZakrevskiy Jul 27 '13 at 14:53
@TZakrevskiy I agree with you about the probable absence of closed form formula. – Did Jul 27 '13 at 14:56

How to solve this recurrence using back substitution: $T(n)=T(n^{1/2})+n$ where T(2)=1

1 Answers1

Linked