I am having problem solving this recurrence. Can anyone help me with this please:
$$ T(n) = 2(T(\sqrt n))^2 , T(1) = 4. $$
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I think the details are missing. $T(n) = 2(T(\sqrt n))^2$ does not hold for $n = 1$. ?? $\endgroup$Inuyasha Yagami– Inuyasha Yagami2021-09-10 04:43:24 +00:00Commented Sep 10, 2021 at 4:43
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Let $S(m) = \log_2 (2T(2^m))$. Then $S(m)$ satisfies the recurrence $$ S(m) = 2S(m-1), \quad S(0) = 3. $$ You can work it out from here.
-
$\begingroup$ Thank you. Can you pleas show you you just came up with $S(m) = 2S(m-1)$? $\endgroup$Avv– Avv2021-09-23 17:04:02 +00:00Commented Sep 23, 2021 at 17:04
-
$\begingroup$ It's a calculation. $\endgroup$Yuval Filmus– Yuval Filmus2021-09-23 18:10:10 +00:00Commented Sep 23, 2021 at 18:10
-
$\begingroup$ Thank you. So, we derive such equations based on linear recurrence formula or this is just change of variable technique please? Can you please give me a reference how to derive such equations? $\endgroup$Avv– Avv2021-09-23 20:00:58 +00:00Commented Sep 23, 2021 at 20:00
-
1$\begingroup$ It's a combination of a change of variables (twice – both input and output) and of slightly changing the recurrence (multiply the original recurrence by 2 on both sides to get a nicer expression). $\endgroup$Yuval Filmus– Yuval Filmus2021-09-23 20:42:29 +00:00Commented Sep 23, 2021 at 20:42
$\begingroup$
$\endgroup$
4
Solving by Substitution
Given,
$T(n)=2(T(\sqrt n))^2$
$T(n)=2(T(n^{1/2}))^2$
$T(n)=2(2(T(n^{1/4}))^2)^2$
$T(n)=2(2(2(T(n^{1/8}))^2)^2)^2$
$T(n)=2.2^2.2^4(T(n^{1/8}))^8$
$T(n)=2^{1+2+2^{2}}(T(n^{1/2^3}))^{2^3}$
Using Summation Formula for Geometric Progression
$T(n)=2^{(2^3-1)}(T(n^{1/2^3}))^{2^3}$
Therefore, for k iterations
$T(n)=2^{(2^k-1)}(T(n^{1/2^k}))^{2^k}$
Now, Assuming that instead of $T(1)=4$, it is given that $T(2)=4$
(Since, $n^{1/2^k}=1$ will be possible when $n=1$ or $\frac{1}{2^k}=0$, which seems invalid as per algorithm)
Therefore, put $n^{1/2^k}=2$
$\frac{1}{2^k}{log_2n}=1$
${2^k}={log_2n}$
Thus,
$T(n)=2^{({log_2n}-1)}(T(2))^{log_2n}$
$T(n)=2^{({log_2n}-1)}(4)^{log_2n}$
$T(n)=2^{({log_2n}-1)}(2)^{2log_2n}$
$T(n)=2^{({log_2n}-1)}2^{log_2{n^2}}$
$T(n)=\frac{2^{({log_2n})}2^{log_2{n^2}}}{2}$
$T(n)=\frac{n^3}{2}$
Thus, $T(n)$ is $O(n^3)$
-
$\begingroup$ Thank you. But it's not given that $T(2) = 4$, can you please explain that a little more? $\endgroup$Avv– Avv2021-09-23 18:23:57 +00:00Commented Sep 23, 2021 at 18:23
-
1$\begingroup$ @Avra If we assume that $T(1)=4$, we have to put $n^{1/2^k}=1$. Take logarithm (of any base) on both sides. It will make ${1/2^k}=0$ which is invalid. $\endgroup$Rohit Singh– Rohit Singh2021-09-23 19:44:39 +00:00Commented Sep 23, 2021 at 19:44
-
$\begingroup$ Thanks. So you just used that invalidity to step upward and try $T(2)=4$ please? $\endgroup$Avv– Avv2021-09-23 19:46:59 +00:00Commented Sep 23, 2021 at 19:46
-
1$\begingroup$ @Avra, Yes it was pure assumption to solve further. $\endgroup$Rohit Singh– Rohit Singh2021-09-23 19:48:29 +00:00Commented Sep 23, 2021 at 19:48