I have no idea how to solve this recurrence problem!

Question

The recurrence equation is below:

$$ {\rm T}\left(n\right) = 2\,{\rm T}\left(n \over 2\right) + 3\,{\rm T}\left(n \over 3\right) + n $$

• I've already tried to find a solution on the internet, but I was unsuccessful.
• My main question is if I should first solve $2\,{\rm T}\left(n/2\right)$ and then $3\,{\rm T}\left(n/3\right)\ ?$.
• Would I be able to use a Recursion Tree or Substitution Method to do it $?$.

Answer 1

The recurrence is $T(n)=2T(\frac n2)+3T(\frac n3)+n$. We have $T(\frac n2)=2T(\frac n4)+3T(\frac n6)+\frac n2$ and $T(\frac n3)=2T(\frac n6)+3T(\frac n9)+\frac n3$. Substituting these in the first equation we get $$T(n)=4T(\frac n4)+9T(\frac n9)+2\frac n2+3\frac n3+n=2T(\frac n2)+3T(\frac n3)+n$$ So the recurrence is solvable using the Master Theorem.

Answer 2

Hint.

Taking a maximal path with $n=2^j3^k$ we have the equivalent recurrence

$$ R(j,k) = 2R(j-1,k)+3R(j,k-1)+2^j3^k $$

or

$$ F(x,y) = 2 y F(x,y) + 3 x F(x,y)+\sum\sum(2x)^j(3y)^k + g_{0,0}(x,y) $$

now assuming $|2x|<1$ and $|3y|<1$ we follow with

$$ (1-2y-3x)F(x,y) = \frac{1}{1-2x}\cdot\frac{1}{1-3y}+ g_{0,0}(x,y) $$

Now assuming null initial conditions

$$ F(x,y) = \frac{1}{1-2y-3x}\cdot\frac{1}{1-2x}\cdot\frac{1}{1-3y} $$

etc.