3
$\begingroup$

I am having problem solving this recurrence. Can anyone help me with this please:

$$ T(n) = 2(T(\sqrt n))^2 , T(1) = 4. $$

$\endgroup$
1
  • $\begingroup$ I think the details are missing. $T(n) = 2(T(\sqrt n))^2$ does not hold for $n = 1$. ?? $\endgroup$ Sep 10, 2021 at 4:43

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you. Can you pleas show you you just came up with $S(m) = 2S(m-1)$? $\endgroup$
    – Avv
    Sep 23, 2021 at 17:04
  • $\begingroup$ It's a calculation. $\endgroup$ 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
    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$ Sep 23, 2021 at 20:42
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you. But it's not given that $T(2) = 4$, can you please explain that a little more? $\endgroup$
    – Avv
    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$ 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
    Sep 23, 2021 at 19:46
  • 1
    $\begingroup$ @Avra, Yes it was pure assumption to solve further. $\endgroup$ Sep 23, 2021 at 19:48

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.