Solution for a recurrence

Question

Need hints/solution to solve for a in terms of n in the equation:

$$a = \sqrt{n} + \sqrt{a}$$

---

I'm actually trying to get and solve the recurrence for the following piece of code:

while (n > 1)
{
    n = (long)Math.Sqrt(n);
    // do something
}

I felt that for this piece of code:

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

and hence arrived at the equation above by writing T(n) = a.

Answer 1

Based on the comments, saying do something is fixed in time, the correct recurrence is $T(n)=1+T(\sqrt n)$ You make one run through with the variable being $\sqrt n$ and then restart. You have not specified what happens when $\sqrt n$ is not an integer. Do you round down, up, or ???. Leaving aside the rounding issues, you should think about what happens to $n=2^k$ where $k$ is a power of $2$