# How to solve recursion T(n)=T(n/2)+T(n/3)+n?

How to solve recursion $$T(n)=T(n/2)+T(n/3)+n$$? I do not really know how to approach this kind of recurrence.

• Use the Akra-Bazzi theorem. – Yuval Filmus Jun 4 at 23:30
• I know the theorem but i do not know how to use it. – RaresG Jun 4 at 23:34

## 1 Answer

This is a straightforward application of the Akra-Bazzi theorem.

You can also show that $$T(n) = \Theta(n)$$ by induction. First, clearly $$T(n) \geq n$$. In the other direction, if we have shown that $$T(m) \leq 6m$$ for $$m < n$$, then $$T(n) \leq 6(n/2 + n/3) + n = 6n.$$ Therefore as long as the base case holds, and if we ignore the fact that $$n/2,n/3$$ are not necessarily integers, we can prove inductively that $$T(n) \leq 6n$$.

• Thank you! If i do not bother you, can you please detail steps for proving it by induction? I applied the Akra-Bazzi after some research, but i need to prove it by induction too. Have a nice day! – RaresG Jun 5 at 10:07
• I'm not going to do the exercise for you. – Yuval Filmus Jun 5 at 10:30