How do I unravel this recurrence relation?
$$T(n) = T(n/2) + T(2n/3) + T(3n/4) + n$$
Here's what I've got so far: $$= T(n/4) + t(n/3) + T(3n/8) + T(n/3) + T(4n/9) + T(n/2) + T(3n/8) + T(n/2) + T(9n/16) + 35n/12 = T(n/4) + 2T(n/3) + 2T(3n/8) + T(4n/9) + 2T(n/2) + T(9n/16) + 35n/12$$
obviously this isn't the way to go. wut do?
$T(n)=T\left(\dfrac{n}{2}\right)+T\left(\dfrac{2n}{3}\right)+T\left(\dfrac{3n}{4}\right)+n$
$T(n)-T\left(\dfrac{n}{2}\right)-T\left(\dfrac{2n}{3}\right)-T\left(\dfrac{3n}{4}\right)=n$
Getting the particular solution part is very easy.
Let $T_p(n)=An$ ,
Then $An-\dfrac{An}{2}-\dfrac{2An}{3}-\dfrac{3An}{4}\equiv n$
$-\dfrac{11An}{12}\equiv n$
$\therefore-\dfrac{11A}{12}=1$
$A=-\dfrac{12}{11}$
$\therefore T_p(n)=-\dfrac{12n}{11}$
But getting the complementary solution part is very difficult.
Since we should handle the equation $T_c(n)-T_c\left(\dfrac{n}{2}\right)-T_c\left(\dfrac{2n}{3}\right)-T_c\left(\dfrac{3n}{4}\right)=0$ .
