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

Question

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.

Answer 1

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$

Answer 2

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+\sqrt[4]n+\sqrt[8]n+\cdots<n+\sqrt n+\sqrt n+\sqrt n+\cdots=n+\sqrt n\lg n,$$ 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$.

Answer 3

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<S(n)<(1+\epsilon)$$ where $\epsilon$ is a constant as small as you want, and $n>n_0$, giving

$$5n<T(n)<5(1+\epsilon)n.$$

Answer 4

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)$

Answer 5

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...