0
$\begingroup$

I tried looking online but found no hints/solutions for this. I don't even post questions on MathSE, so please help me put the question correctly if needed.

I'm trying to solve the following recurrence relation containing a fourth root:

$T(n) = 1 + T(n^{1/4}).$

I did the obvious substitution to get

$T(m^4) = 1 + T(m).$

But now what? Also, I thought to rewrite this as:

$k^4= 1 + k.$

But how is this equation solved? (Yes I know this is not correct. Wrote that way to find any way to solve it)

I have been mostly ignoring the round up and down situation and assumed that the fourth root will continue to give me an integer, yet we can assume that we round up. Further, T(1) = T(2) = 1. In general, if the 4th root of n is between 1 and 2 (both inclusive), we can take T(n) to be 1.

$\endgroup$
  • $\begingroup$ Will the down voter tell what can I improve in the question? $\endgroup$ – displayName Sep 11 '17 at 16:05
  • $\begingroup$ Do you round the fourth root down or up? What is the starting value? So is $T(3)=1+T(1)$ or $1+T(2)?$. If you round up $T(2)=1+T(2)$ fails. If I don't have a better idea, I first compute a bunch of values and see if I find inspiration. Have you done that? $\endgroup$ – Ross Millikan Sep 11 '17 at 16:06
  • $\begingroup$ You can't do your rewrite to $k^4=1+k$ because you are assuming that $T(n)=n$ when you do that, which is not true. If you round up you need to define $T(2)$ as a base case as well, because of what I said in my previous comment. $\endgroup$ – Ross Millikan Sep 11 '17 at 16:27
  • $\begingroup$ @RossMillikan: Updated. $\endgroup$ – displayName Sep 11 '17 at 16:46
1
$\begingroup$

For all the $n$ with $2 \lt n \le 16$ we get $T(n)=2$. Once we get to $17$ have $T(n)=1+T(3)=3$ until we get to $81$, but then we have $T(n)=1+T(4)=3$ until $5^4$ and the value doesn't increase until $n \gt 16^4=2^{16}=65536$, when it gets all the way to $4$. It stays $4$ until $n \gt 65536^4=2^{64}=18446744073709551616$

Claim: for $2^{4^k}+1 \le n \le 2^{4^{k+1}}, T(n)=k+2$ The proof is by induction, following the computation above.

$\endgroup$
  • $\begingroup$ How do I get k in terms of n? $\endgroup$ – displayName Sep 11 '17 at 16:54
  • $\begingroup$ You take the log of the log and divide by $2$. $\endgroup$ – Ross Millikan Sep 11 '17 at 17:00

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.