Solving a recurrence with substitution method that involves the square root

Question

How would you guys go along with solving a recurrence relation with the substitution method, that has the square root in it? Like

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

Answer 1

This is how I actually solved it:

First, there is obviously a lower bound in ?(n)

Also, I notice that it expands to n + n^1/2 + n^1/4... The sizes decrease more quickly than n + n/2 + n/4..., and I know that has an upper bound in O(n), So T(n) must be in O(n), too.

Since T(n) is in ?(n) and in O(n), then it's also in ?(n).

So now it's solved -- we know the answer. If this is a test question, though, then you'd have to write a proof of that upper bound, which you could accomplish a number of different ways.

I would do it by induction. Given a constant A and some n such that:

T(n) < An

Then we have:

T(n²) = T(n) + n² < An + n² = (A/n+1)n²

And if A and n are sufficiently large, then (A/n + 1) < A, so

T(n²) < An²