1
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – RaresG Jun 5 at 10:07
  • $\begingroup$ I'm not going to do the exercise for you. $\endgroup$ – Yuval Filmus Jun 5 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.