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.
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} &lt; 1$.
When $a^{-c} + b^{-c} = 1$, the answer is likely $T(n) = \Theta(n^c\log n)$.