1

$$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

Samrat Mukhopadhyay
  • 16,277
basant
  • 11
  • 2
    What happens in your relation when $3n/4$ or $n/3$ are not integers ? Do you round down or up or ... ? – minar Aug 10 '13 at 07:47

1 Answers1

0

$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$ .

doraemonpaul
  • 16,178
  • 3
  • 31
  • 75