Solving the recurrence relation $T(n) = 2T(n^\frac{1}{2}) + c$

Question

I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$?

I've assumed $T(1)$ and $c$ are constants. So this is when $n = 2$?

Answer 1

Do the variable change $n = 2^{2^k}$, so you can take square roots every time. Your base case is $n = 2$, i.e., $k = 0$. You get a simple recurrence for $T(2^{2^k})$.

Answer 2

What vonbrand is suggesting is if you write $n=2^{2^k}$, then $$ \sqrt{n} = \sqrt{2^{2^k}}=(2^{2^k})^{1/2}=2^{2^{k-1}} $$ so your recurrence may be written as $$ T(2^{2^k})=2T(2^{2^{k-1}}) + c $$ and we can do this substitution again (the blue part) to get $$ \begin{align} T(2^{2^k})&=2\;\color{#0000FF}{T(2^{2^{k-1}})} + c\\ &=2(\color{#0000FF}{2\;T(2^{2^{k-2}}) + c}) + c\\ &= 2^2T(2^{2^{k-2}})+2c + c \end{align} $$ If you continue doing these substitutions until you have the term $T(2^{2^0}) = T(2)$ (assuming you know $T(2)$. Note that $T(1)$ is no help here.), you'll have an equation with the $T$ term only on the left, and so will have a solution, in the form $T(2^{2^k}) =\ $ some expression without any T's, which is of course what you were looking for.

---

Here's another way to look at this problem. Instead of working from the top down, let's do it from bottom up to see if we can guess an answer.

We have $$ T(2^{2^k})=2T(2^{2^{k-1}}) + c $$ and let's call the value $T(2)=a$. Working up, we have $$ \begin{align} T(2^{2^0})=T(2) &= a\qquad\text{so}\\ T(2^{2^1})=T(4) &= 2T(\sqrt{4}) + c = 2T(2)+c = 2a+c\qquad\text{so}\\ T(2^{2^2})=T(16) &= 2T(4)+c = 2(2a+c)+c = 4a+2c+c\\ T(2^{2^3})=T(256) &= 2T(16)+c = 2(4a+2c+c)+c = 8a+4c+2c+c \end{align} $$ and we see a pattern developing: $$ \begin{align} T(2^{2^k}) &= 2^ka+2^{k-1}c+2^{k-2}c+\cdots + 2c+c\\ &= 2^ka+(2^k-1)c \end{align} $$ Finally, we tidy this up a bit. Since we chose $n=2^{2^k}$, we'll have $\log_2n = 2^k$ so for those numbers, we can rewrite our guess as $$ T(n) = (\log_2n)(T(2)+c)-c $$ One final remark is in order. The solution we arrived at was a guess, based on the pattern we saw developing. To be rigorous, we should prove that our guess was right. This could be done by induction on $k$. It's not trivial, but it isn't all that difficult.

Answer 3

Let's set $R(k)=T(2^k)$. Substituting to the original formula we get $$R(k)=T(2^k)=2T(\sqrt{2^k})+c=2T(2^{k/2})+c=2R(\frac{k}{2})+c.$$ The master theorem tells us that $R(k)\in O(k)$. So let's try setting $$R(k)=ak+b$$ and solve $a$ and $b$: \begin{align} ak+b &= 2(a\frac{k}{2}+b)+c \\ ak + b &= ak+2b+c \\ b &= - c \\ \end{align} So $a$ can be arbitrary, and $T(n)=R(\log_2 n)=a\log_2 n - c$.