1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You should probably add the restriction that $n>1$, otherwise we get $T(1)=2T(\sqrt 1)+c$ which implies $c=-T(1)$. Because of the square root, it's more meaningful to start with $T(2)$ instead of $T(1)$. $\endgroup$ – Petr Pudlák May 3 '13 at 7:03
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Or could you possibly expand on your answer? I'm not sure what you mean? $\endgroup$ – SexySarah May 2 '13 at 21:53
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't know what T(2) is, but if I say T(2^2k) = 2, then solve for k, i.e., k=1, then the result I reach is just 2. Is this correct? $\endgroup$ – SexySarah May 3 '13 at 4:38
  • $\begingroup$ @SexySarah I've added a section. Perhaps it will help. $\endgroup$ – Rick Decker May 3 '13 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.