Solving a recurrence relation: can't figure out how to convert from summation

Question

I am really struggling to solve this recurrence.

$$ T(n) = T(\sqrt{n}) + n. $$

I am asked to give asymptotic upper and lower bounds for $T(n)$. I am free to use any method to arrive at my answer, whether it be iteration method, substitution method, or master method. I'm not quite comfortable with substitution method (as I don't even have any idea as what to guess), and the master method doesn't apply here. I wrote out a recursion tree, and I now believe that the solution can be described as:

$$ \sum_{i=0}^{n} \frac{1}{c^{2^{i}}} $$

However, I can't (for the life of me) figure out what it sums to. Any help would GREATLY be appreciated, or if someone could explain how to do it via substitution method would also be appreciated (either one). Thanks in advance!

Answer 1

Well ... if you're willing to believe that $T$ is an increasing function, then it's probably enough, for these estimates, to work with numbers of the form $$ n_k = (((2^2)^2)\ldots)^2, $$ where the $2$ is squared $k$ times. Then you get that $$ T(n_k) = T(n_{k-1}) + n_k $$ and unrolling this gives just the kind of expression you've got (except that I've used "2" instead of $c$).

I can't tell you what it sums to either, but that's not what you were asked. You were asked to give an asymptotic upper bound, which is just something that it's no greater than. Assuming that $c > 1$ (because it is), we have $c^{2^i} > c^i$, for instance, so $$ \frac{1}{c^{2^i}} < \frac{1}{c^i} $$ and you can (upper) bound your series with a simple geometric series.

There is the question of "what is $c$ in terms of $n$?", and the answer looks like something like an iterated logarithm, but I haven't worked through that.

Answer 2

Hint.

From

$$ T(n) = T(\sqrt n) + n $$

we have

$$ \mathcal{T}(\ln n) - \mathcal{T}\left(\frac{\ln n}{2}\right) = n $$

or making $z = \ln n$

$$ \mathcal{T}(z) - \mathcal{T}\left(\frac{z}{2}\right) = e^z $$

and also

$$ \mathbb{T}(\log_2 z) - \mathbb{T}(\log_2 z-1) = e^z $$

and now making $\log_2 z = m$

$$ \mathbb{T}(m) - \mathbb{T}(m-1) = e^{2^m} $$

now this is a linear nonhomogeneous difference equation that can be solved as

$$ \mathbb{T}(m) = \mathbb{T}_h(m)+\mathbb{T}_p(m) $$

or

$$ \mathbb{T}(m) =\mathbb{T}(0) +\sum_{k=1}^{m}e^{2^k} $$

The return to $T(n)$ is left to the reader.

Answer 3

I am asked to give asymptotic upper and lower bounds for ().

Then let us do exactly that...

First, assuming, as is customary, that every $T(k)$ is nonnegative, one sees that $T(n)\geqslant n$.

Next, let us look for some upper bound $$T(n)\leqslant an+b$$ that would be hereditary. This happens if $$(a\sqrt n+b)+n\leqslant an+b$$ for every $n$ large enough, hence, $a=2$ works for every $n\geqslant4$.

This shows that $T(n)\leqslant 2n+b$ for every $n$, as soon as $b$ is large enough for this inequality to hold for $n<4$.

Thus, for every $n$, $$n\leqslant T(n)\leqslant 2n+b$$ in particular, $$T(n)=\Theta(n)$$ Nota: The above is the most elementary approach vailable to solve the question. Refining it slightly yields the stronger statement that $T(n)\sim n$, that is, $$\lim_{n\to\infty}\frac{T(n)}n=1$$ To prove this, one can for example study the upper bound $T(n)\leqslant n+c\sqrt n$ for $c\geqslant2$...