recureence relation $T(n,m) = 2T(\frac{3n}{2},\frac{m}{2})+O( n^2 )$

Question

What is asymptotic order of $T(n,m)$ where

$$T(n,m) = 2T\left(\frac{3n}{2},\frac{m}{2}\right)+O( n^2 )$$

Answer 1

If we expand the recurrence relation, we have:

$$T(n, m) = n^2 + 2*(\frac{3}{2})^2*n^2 + 2^2*(\frac{3}{2})^3*n^2 + \dots + 2^{\lg{m}}*((\frac{3}{2})^{\lg{m}})^2*n^2$$

So

$$T(n, m) = n^2 * \Big(\sum_{i = 0}^{\lg{m}}{2^i*\big((\frac{3}{2})^i\big)^2\Big)}=n^2 * \Big(\frac{3*(1-(\frac{3}{2})^{\lg{m}})}{1-\frac{3}{2}}\Big)$$

In the above equation the summation is a geometric series and all log operations are based on 2. At last:

$$T(n, m) = n^2 * \Big(6*\big((\frac{3}{2})^{\lg{m}}-1\big)\Big)=\Theta\Big(n^2*(\frac{3}{2})^{\lg{m}}\Big)$$