Closed form for $T(n) = n(T\left(\tfrac {n}{2}\right))^2$ I am trying to find a closed form for the following: $$T(n) = n(T\left(\tfrac {n}{2}\right))^2$$, with $T(1)=1/3$.
I set $T(n)=T(2^m)=S(m)$ and then transformed the range of $S(m)$ to set $U(m)=log(S(m))$.
I got $\displaystyle U(m)=c_1*2^m+c_2+c_3*m$.
I am having trouble transforming back and solving for the constants with the initial condition given.
Please help!
 A: Setting $n=2^m$, and $g(m) = T(2^m)$, we get that
$$g(m) = 2^m g^2(m-1)$$
Setting $f(m) = \log_2(g(m))$, we get
\begin{align}
f(m) & = m + 2 f(m-1)\\
& = m + 2(m-1) + 4 f(m-2)\\
& = m + 2(m-1) + 4(m-2) + 8 f(m-3)\\
& = m + 2(m-1) + 4(m-2) + 8 (m-3) + 16 f(m-4)\\
& = 2^m f(0) + \sum_{k=0}^{m-1} 2^k(m-k) = m (2^{m+1}-1) - 2^{m+1}m + 2^{m+1} - 2 - 2^m \log_2(3)\\
& = 2^{m}(2-\log_2(3)) - m -2\\
& = (2-\log_2(3))n - \log_2(n) - 2
\end{align}
Hence,
$$T(n) = \dfrac{2^{(2-\log_2(3))n}}{4n} = \dfrac{4^n}{4 n \cdot 3^n} = \dfrac{(4/3)^{n-1}}{3n}$$
A: From $T(n) = n(T(n/2))^2$,
$nT(n) = n^2(T(n/2))^2
= (nT(n/2))^2
= 4((n/2)T(n/2))^2
$.
Let $cU(n) =  n T(n)$, where $c$ will soon be determined.
Then $cU(n) = 4(cU(n/2))^2 = 4c^2(U(n/2))^2$,
or $U(n) = 4c(U(n/2))^2$.
If we set $c = 1/4$,
so $U(n) = 4n T(n)$,
$U(n) = (U(n/2))^2$.
Iterating $m$ times.
$U(n) = (U(n/2^m))^{2^m}$.
Setting $n = 2^m$,
$U(2^m) = (U(1))^{2^m}$,
or
$4\cdot 2^m T(2^m) = (4 T(1))^{2^m}
= (4/3)^{2^m}
$
so
$T(2^m) = 2^{2\cdot 2^m - 2 - m}/3^{2^m}
= 2^{2^{m+1} - 2 - m}/3^{2^m}
$.
Setting $2^m = n$,
$T(n) 
= 2^{2n - 2 - m}/3^{n}
= \frac{4^{n-1}}{n 3^n}
$.
Since this is the same as Marvia's result,
there is a good chance that it is correct.
A: I'll generalize my solution
to solve the recurrance
$T(n) = n^p T^q(n/r)$,
where $p, q$, and $r$ are positive integers.
I want to convert this to the form
$U(n) = U^q(n/r)$.
To do this,
let $T(n) = a n^b U(n)$,
where we will determine $a$ and $b$.
Substituting this,
$a n^b U(n) = n^p (a (n/r)^b U(n/r))^q
=n^p a^q n^{bq} U^q(n/r)/r^{bq}
= (a^q/r^{bq}) n^{p+bq}U^q(n/r)
$.
To get this in the form we want,
we must have
$a = a^q/r^{bq}$
and
$b = p+bq$.
From the second one,
$b = p/(1-q)$.
Using the first one,
$r^{bq} = a^{q-1}$
or $a = r^{bq/(q-1)} = r^{-pq/(1-q)^2}$.
As a check, in the original problem,
$p=1$, $q=2$, and $r=2$
for which we get
$b = -1$ and $a = 2^{-2}=1/4$,
so $T(n) = (1/(4n))U(n)$.
From $U(n) = U^q(n/r)$,
$U(n) = U^q(n/r) = U^{q^2}(n/r^2)
... = U^{q^{2^m}}(n/r^{2^m})
$.
Setting $n = r^{2^m}$,
$U(r^{2^m}) = U^{q^{2^m}}(1)$.
To get $T(n)$ from this,
set $n = r^{2^m}$ in
$T(n) = a n^b U(n)$.
so $T(r^{2^m}) = a r^{b 2^m} U^{q^{2^m}}(1)
= a r^{b 2^m} (T(1)/a)^{q^{2^m}}
= a^{1-q^{2^m}}r^{b 2^m} T^{q^{2^m}}(1)
$.
At this point, to simplify,
I will assume $q = r$,
so the recurrence has the same exponent as scale factor.
You are welcome to do the algebra for the general case.
Using $n = r^{2^m} = q^{2^m}$,
$b = p/(1-q) = p/(1-r)$,
and
$a = r^{-pq/(1-q)^2} = r^{-pr/(1-r)^2}$
this becomes
$T(n)= a^{1-n} n^b T^n(1)
=r^{(n-1)pr/(1-r)^2} n^{p/(1-r)}T^n(1)
$.
For the original case,
where $p=1$, $q=2$, and $r=2$,
this becomes
$T(n) = 2^{2(n-1)} n T^n(1)
=(4T(1))^n/(4n)
$.
