Solving recurrence equation $T(n)=T(n^{2/3})+17$

How can the following recurrence equation be solved by one of three main ways:

$$T(n)=T(n^{2/3})+17$$

I have tried solving it by the iteration way. However it does not work for me since I can't find the equation with $$i$$, i.e the generic equation.

• Have you tried applying any of the methods listed here? – dkaeae Mar 15 at 16:32
• The answer will be proportional to the number of times that you have to raise a number to the power $2/3$ until it gets below an arbitrary constant. I'm sure you can work that out on your own. – Yuval Filmus Mar 16 at 12:24
• I’d recommend using a spreadsheet to find Say T(1000); that should give you some idea. – gnasher729 Mar 16 at 13:58

We can do this pretty easily with a change of variables here. Let $$n = 2^{(3/2)^k}$$ we then can rewrite $$T(n)$$ as: $$S(k) = S(k - 1) + 17$$ We have $$S(k) = O(k)$$. Then converting $$k$$ back to $$n$$ we have: $$k = \log_{3/2} \log_2 n$$ Thus, $$T(n) = O(\log \log n)$$.

• Is it also $T(n) = \theta (\log_{3/2} \log_2 n)$? – John D Mar 21 at 9:59

This post answers the original version of the question, where the recurrence relation is

$$T(n)=T\left(\frac{n^2}{3}\right)+17$$

The recurrence relation is somewhat unconventional. Here is an outline to solve it.

Suppose $$n\ge 6$$. Let $$n=3\cdot2^{2^{m}}$$, where $$m=\log_2(\log_2\frac n3)\ge0$$.

\begin{align} T(n) &=T\left(3\cdot2^{2^{m}}\right) =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m}}\right)}\right)-17\\ &=T\left(3\cdot2^{2^{m-1}}\right)-17 =T\left(\sqrt{3\cdot3\left(\cdot2^{2^{m-1}}\right)}\right)-2\cdot17\\ &=T\left(3\cdot2^{2^{m-2}}\right)-2\cdot17 =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m-2}}\right)}\right)-3\cdot17\\ &=\cdots\\ &=T\left(3\cdot2^{2^{m-\lceil m\rceil}}\ \right)-\lceil m \rceil\cdot 17 \end{align}

Since $$-1\lt m-\lceil m\rceil\le0$$, $$3\sqrt2\lt3\cdot2^{2^{m-\lceil m\rceil}}\le6.$$ So $$T(n)\sim -17\log_2(\log_2 n)$$ when $$n$$ goes to $$\infty$$.

Here are two related exercises.

Exercise 1. What is the recurrence relation for function $$S$$ such that $$S(n)=T(3n)$$?

Exercise 2. What is the asymptotic behavior of $$T(n)$$ if $$n$$ goes to 3 from above, assuming $$T$$ is continuous?

• Who edit the question, change the whole exercise. It should be n^(2/3). – John D Mar 16 at 9:46
• I am afraid that you wrote it as n^2/3, as shown in the first version, which was changed it to n^(2/3) more than 14 hours later. – Apass.Jack Mar 16 at 11:06
• Question clearly was posted as T(n squared divided by 3), changed to T(n followed by some weird stuff) by OP then changed to T(cube root of n squared). Original is the most interesting one :-) – gnasher729 Mar 16 at 14:05

Another similar answer to Apass.Jack on the "original" question.

First flip the function around:

$$T\left(\frac{n^2}{3}\right) = T(n) - 17$$

Convert it to an intelligible form by a change of variables where $$m = \tfrac{n^2}{3}$$:

$$T(m) = T(\sqrt{3m}) - 17$$

Try another change of variables where $$m = 3 \cdot 2^{2^\omega}$$. We get:

$$T(\omega) = T(\omega - 1) - 17$$

Thus $$T(\omega) = -17\omega$$. Now we work backwards:

\begin{align*} T(\omega) & = -17 \omega\\ T(m) & = -17 \log_2 \log_2 (m / 3)\\ T(n^2 / 3) & = -17 \log_2 \log_2 (n^2 / 9)\\ T(n) & = -17 \log_2 \log_2 (n / 3)\\ \end{align*}

This assumes a base case of $$T(\omega = 1) = -17$$ or the following other assumed base cases:

\begin{align*} T(\omega = 1) &= -17\\ T(m = 6) & = -17\\ T(n = 6) & = -17 \end{align*}