Recurrence relation with unequal division

417 Views Asked by At

$$T(n) = T(3n/4) + T(n/3) + n$$ Please help me solve this recurrence relation. Somehow even Akra_Bazzi method doesn't seem to work in this case

1

There are 1 best solutions below

1
On

$T(n)=T\left(\dfrac{3n}{4}\right)+T\left(\dfrac{n}{3}\right)+n$

$T(n)-T\left(\dfrac{3n}{4}\right)-T\left(\dfrac{n}{3}\right)=n$

Getting the particular solution part is very easy.

Let $T_p(n)=An$ ,

Then $An-\dfrac{3An}{4}-\dfrac{An}{3}\equiv n$

$-\dfrac{An}{12}\equiv n$

$\therefore-\dfrac{A}{12}=1$

$A=-12$

$\therefore T_p(n)=-12n$

But getting the complementary solution part is very difficult.

Since we should handle the equation $T_c(n)-T_c\left(\dfrac{3n}{4}\right)-T_c\left(\dfrac{n}{3}\right)=0$ .