Cómo resolver esta recurrencia $t(n) = ( 2^n )( t(n/2) )^2$ con $t(1)=1$ ?

Question

Me he preguntado cómo resolver esta recurrencia pero no llego a ninguna solución factible. ¿Cómo puedo hacerlo?

Answer 1

Esquema:

Intenta mirar primero el caso $n=2^k$ y resolver la recurrencia $$ T(2^k) = 2^{2^k} T(2^{k-1})^2. $$ Ampliando, se obtiene $$ T(2^k) = 2^{2^k} (2^{2^{k-1}})^2 T(2^{k-2})^4 = 2^{2\cdot 2^k} T(2^{k-2})^4 = 2^{3\cdot 2^k} T(2^{k-3})^8 = \cdots = 2^{k\cdot 2^k} T(2^{0})^{2^k} $$ de manera que se obtiene, mediante $T(2^0) = 1$ que $$ T(2^k) = 2^{k 2^k}. $$ Ignorando los suelos y todo lo demás, deberías obtener algo parecido a $$ T(n) = 2^{n\log n} = n^n. $$