# Recurrence and Time complexity

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

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

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

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.

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

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

• Thank you. But it's not given that $T(2) = 4$, can you please explain that a little more?
– Avv
Sep 23 '21 at 18:23
• @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. Sep 23 '21 at 19:44
• Thanks. So you just used that invalidity to step upward and try $T(2)=4$ please?
– Avv
Sep 23 '21 at 19:46
• @Avra, Yes it was pure assumption to solve further. Sep 23 '21 at 19:48