Asymptotic upper bound $T(n)=(T(n−1))^2$

Question

The question is to find asymptotic upper bound for recurrence:

$T(n)=(T(n−1))^2$

$T(n) = \text{n for n} \leq 2$

---

My attempt:

I've tried to use substitution method and getting:

$T(n) = (T(n-1))^2 = ((T(n-2))^2)^2 = (((T(n-3))^2)^2)^2$ etc.

I couldn't find a way to express n number of powers of 2's.

Can you explain in formal way? Please.

Answer 1

$T(n) = T(n-k)^{2^k}$ (for $k < n-2$)

you can prove this by induction:

for k=1: $$T(n) = T(n-1)^2$$

and the induction step:

$$T(n) = T(n-k)^{2^k} = (T(n-k-1)^2)^{2^k}=T(n-(k+1))^{2^{k+1}}$$

now take $k=n-3$: $$T(n) = T(n-(n-3))^{2^{n-3}} = T(3)^{2^{n-3}} = 2^{2^{n-2}}$$