Squaring recurrence under integer halving
= Squaring recurrence under integer halving
{title2=$T(n)=2^{2^{d(n)}-1}$}
For $T(n)=1$ at $n\leq3$ and $T(n)=2T(\lfloor n/2\rfloor)^2$ otherwise, put $d=\max(0,\lfloor\log_2n\rfloor-1)$ for <positive integer> $n$. Taking <logarithms> gives $S(n)=1+2S(\lfloor n/2\rfloor)$, hence $S(n)=2^d-1$ and $T(n)=2^{2^d-1}$. These constant-value plateaux have exponential envelopes $2^{\Theta(n)}$, but do not justify $\Theta(2^{n/2})$ for all <integer> inputs.