Closed form for $T(n) = n(T\left(\tfrac {n}{2}\right))^2$

Question

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!

Answer 1

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}$$

Answer 2

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.

Answer 3

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) $.