# Find the asymptotic bound for the recurrence relation: $T(n) = T(\sqrt{n}) + 5n$

I've tried to expand the recursion:

$$T(n) = T(n^{\frac{1}{2}}) + 5n = T(n^{\frac{1}{4}}) + 5(n^{\frac{1}{2}} + n) = T(n^{\frac{1}{8}}) + 5(n^{\frac{1}{4}} + n^{\frac{1}{2}} + n)$$

We have a total of $$\lfloor\log_2(n)\rfloor + 1$$ elements in the recursion. So we can easily find an upper bound: $$T(n) = O(n\cdot \log_2(n))$$

The thing is, I'm not sure it's a tight upper bound. More over, I haven't been able to reach a tight lower bound from the recursion. I've tried to, but I didn't get to the same assymptotic bound I've found above.

Any help would be appreciated.

• These T(n) = T(sqrt(n)) + ... questions are really coming into fashion, right? Apr 17 at 23:21

Taking the square root of $$n$$ halves the number of bits, so you indeed halve that number $$\lg n$$ times before the iterated square root falls below some predefined constant (say $$4$$).

Now we can write

$$n+\sqrt n+\sqrtn+\sqrtn+\cdots which is $$O(n)$$.

Justification:

With $$n=m^2$$, $$\sqrt n\lg n\le n$$

becomes $$2m\lg m\le m^2$$ or $$2\lg m\le m,$$

which is true as of $$m=4$$.

• Great answer. For the lower bound, is it safe to claim that $T(n) \ge 5n \ge n$, so $T(n) = \Omega(n)$, and in total we get $T(n) = \Theta(n)$? Mar 21 at 8:44
• @Yoxbox: yes it is.
– user16034
Mar 21 at 10:54

You can use induction to show that $$T(n) = O(n)$$.

More concretely, try to prove using induction that you can find a $$c\in \mathbb{R}^+$$ and $$n_0\in \mathbb{N}$$ such that for all $$n>n_0$$, it will hold that $$T(n) < cn$$.

Basically, substituting this in the induction will reduce your recurrent formula into a simple equation that you will need to solve to find the suitable constants $$c$$ and $$n_0$$.

Hint: try picking $$n_0>4$$

• Or try a really big n, like n = 2^1024 (over 300 decimal digits). Mar 19 at 22:09

Dropping the factor $$5$$ and reducing by $$S(n):=\dfrac{T(n)}{5n}$$, and with $$S(10)=0$$ (arbitrarily):

$$S(100)=\frac{S(10)}{10}+1=1$$ $$S(10000)=\frac{S(100)}{100}+1=1.01$$ $$S(100000000)=\frac{S(10000)}{10000}+1=1.000101$$ $$S(10000000000000000)=\frac{S(100000000)}{100000000}+1=1.00000001000101$$

It is clear that $$S(n)$$ gets closer and closer to $$1$$.

$$1 where $$\epsilon$$ is a constant as small as you want, and $$n>n_0$$, giving

$$5n

We want to find, $$T(n) = T(\sqrt{n}) + 5n$$

Assume $$T(\epsilon) = c > 1$$, $$\epsilon > 1$$ .

So $$T(n) = T(\epsilon^{2k}) \\ = c + 5(\epsilon^2 + \epsilon^4 + \cdots + \epsilon^{2k}) \\ < c + 5((k-1)\epsilon^{2(k-1)} + \epsilon^{2k})\\ = c + 5 (o(\epsilon^{2k}) + \epsilon^{2k}) = O(5n)$$

• @gnasher729 here you can try $2^{1024}$. Just play with the exponent, and leave $2$ for this moment. You will add some numbers with $1024$ bit and all other things to be added can be summed up to $600$ bit at most. Mar 21 at 18:03
• If with $5n$ you mean "asymptotically no greater than $5n$", you are wrong.
– user16034
Mar 21 at 21:07
• @Yves Why? Where is the problem? Mar 21 at 21:34
• It is always greater than $5n$.
– user16034
Mar 22 at 8:44

Hint.

$$T\left(2^{\log_2 n}\right) = T\left(2^{\frac 12\log_2 n}\right)+5n$$

or recasting

$$R(z) = R\left(\frac z2\right)+5\cdot 2^z$$

and recasting again

$$C(m) = C(m-1) + 5\cdot 2^{2^m}$$

and after solving, backwards...