# On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$

Consider the recurrence $$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c).$$ What is the condition on $$a,b$$ that guarantees $$T(n)=O(n^c)$$?

With substitution I get $$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c)\le (\tfrac{n}{a})^c + (\tfrac{n}{b})^c + n^c = n^c ((\tfrac{1}{a})^c + (\tfrac{1}{b})^c + 1)$$ I need $$(\frac{1}{a})^c + (\frac{1}{b})^c + 1$$ to be less than one if I want to show that it is $$\le n^c$$. So $$\frac{1}{a^c} + \frac{1}{b^c} \le 0$$. But I have trouble with that and I don't know if my idea of showing this is right.

• Are you familiar with the Akra–Bazzi theorem? – Yuval Filmus Mar 14 at 11:09
• @YuvalFilmus no, I'll look that up. – Nerwena Mar 14 at 11:17

## 1 Answer

Suppose that $$T(n) = T(n/a) + T(n/b) + n^c.$$ Let's try to prove by induction that $$T(n) \leq Mn^C$$: $$T(n) \leq M(n/a)^c + M(n/b)^c + n^c = \left((a^{-c} + b^{-c})M + 1 \right) n^C.$$ Therefore we need $$(a^{-c} + b^{-c})M + 1 \leq M$$, which we can satisfy as long as $$a^{-c} + b^{-c} < 1$$.

When $$a^{-c} + b^{-c} = 1$$, the answer is likely $$T(n) = \Theta(n^c\log n)$$.