1
$\begingroup$

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.

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

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

$\endgroup$

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.