0
$\begingroup$

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.

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

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

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

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?

$\endgroup$
  • $\begingroup$ Who edit the question, change the whole exercise. It should be n^(2/3). $\endgroup$ – John D Mar 16 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$ – Apass.Jack Mar 16 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 Mar 16 at 14:05
0
$\begingroup$

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*}$$

$\endgroup$

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.