Solve recurrence relation $T(n) = n\cdot T(n/2)^2 $

Question

How would you solve the recurrence $T(n) = n\cdot T(n/2)^2$? Could you use the master method? Or do you have to use iteration?

Answer 1

We have $$4nT(n) = \left(4\frac{n}{2}T(n/2)\right)^2$$ so that $$F(n) = F(n/2)^2 $$ where $F(n) = 4nT(n).$

Then take logs $$\ln(F(n)) = 2\ln(F(n/2)) $$

so that we have $$ G(n) = 2G(n/2)$$ where $G(n) = \ln(F(n)).$

The solution to this is obvious: when $n$ doubles, so does $G.$ Thus it is a linear function $$ G(n) = an.$$

Unwinding the transformations gives $F(n) = e^{an}$ and $T(n) = \frac{e^{an}}{4n}.$

As for your question about whether the master method works, I'm only familiar with that as a theorem about asymptotics, but when you take logs of the initial equation it immediately becomes a recurrence of that type and you can conclude that the log of the solution is $\Theta(n).$