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


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.

  • 2
    $\begingroup$ Have you tried applying any of the methods listed here? $\endgroup$
    – dkaeae
    Commented Mar 15, 2019 at 16:32
  • $\begingroup$ 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. $\endgroup$ Commented Mar 16, 2019 at 12:24
  • $\begingroup$ I’d recommend using a spreadsheet to find Say T(1000); that should give you some idea. $\endgroup$
    – gnasher729
    Commented Mar 16, 2019 at 13:58

3 Answers 3


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

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

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


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?

  • $\begingroup$ Who edit the question, change the whole exercise. It should be n^(2/3). $\endgroup$
    – John D
    Commented Mar 16, 2019 at 9:46
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Mar 16, 2019 at 11:06
  • 1
    $\begingroup$ 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 :-) $\endgroup$
    – gnasher729
    Commented Mar 16, 2019 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*}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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