1
$\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 '19 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 '19 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 '19 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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it also $T(n) = \theta (\log_{3/2} \log_2 n)$? $\endgroup$ – John D Mar 21 '19 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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Who edit the question, change the whole exercise. It should be n^(2/3). $\endgroup$ – John D Mar 16 '19 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. Mar 16 '19 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 '19 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*}$$

| cite | improve this answer | |
$\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.