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 '21 at 4:43
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 '21 at 17:04
  • $\begingroup$ It's a calculation. $\endgroup$ Sep 23 '21 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 '21 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 '21 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 '21 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 '21 at 19:44
  • $\begingroup$ Thanks. So you just used that invalidity to step upward and try $T(2)=4$ please? $\endgroup$
    – Avv
    Sep 23 '21 at 19:46
  • 1
    $\begingroup$ @Avra, Yes it was pure assumption to solve further. $\endgroup$ Sep 23 '21 at 19:48

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.