How to solve this recurrence $t(n) = ( 2^n )( t(n/2) )^2$ with $t(1)=1$?

Question

I have been wondering about how to solve this recurrence but I don't get to any feasible solution. How can I do it?

Answer 1

Outline:

Try to look first at the case $n=2^k$, and solve the recurrence $$ T(2^k) = 2^{2^k} T(2^{k-1})^2. $$ Expanding, you get $$ 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} $$ so that you obtain, using $T(2^0) = 1$, that $$ T(2^k) = 2^{k 2^k}. $$ Ignoring the floors and everything, you should get something along the lines of $$ T(n) = 2^{n\log n} = n^n. $$