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.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Have you tried applying any of the methods listed here? $\endgroup$– dkaeaeCommented 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$– Yuval FilmusCommented 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$– gnasher729Commented Mar 16, 2019 at 13:58
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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 DCommented Mar 21, 2019 at 9:59
$\begingroup$
$\endgroup$
3
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?
-
$\begingroup$ Who edit the question, change the whole exercise. It should be n^(2/3). $\endgroup$– John DCommented 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$ Commented Mar 16, 2019 at 14:05
$\begingroup$
$\endgroup$
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*}$$