Recurrence Relation Theta bound

Question

I have a recurrence of type

T(n)T(n) = T(n/2)T(2n) − T(n)T(n/2)

How to find a theta bound for T(n)?

Answer 1

Note that $$\frac{T(2n)}{T(n)}=1+\frac{T(n)}{T(n/2)}$$ hence $$\frac{T(2^{k+1})}{T(2^k)}=k+\frac{T(2)}{T(1)},$$ that is, $$T(2^k)=(k+c)(k-1+c)\cdots (1+c)T(1).$$ Thus, $$T(2^k)=k^{k+o(1)},$$ and $$\log T(n)=\Theta((\log n)(\log\log n)).$$