Solving a recurrence having different sub-problem size using Master Theorem

Question

Suppose I need to solve below recurrence using Master Theorem, $$T(n) = T(n/b_{1}) + T(n/b_{2})+ f(n)$$

Can I simplify the recurrence as below:

$$T(b_{2}n/b_{2}b_{1}) + T(b_{1}n/b_{1}b_{2}) = b_{2}T(n/b_{2}b_{1}) + b_{1}T(n/b_{1}b_{2}) =(b_{1}+b_{2})T(n/b_{2}b_{1})$$

i.e. $$T(n) = (b_{1}+b_{2})T(n/b_{2}b_{1}) + f(n)$$

And, then apply Master Theorem/method. If this is not correct, would you pls give me a hint on how to approach this.

Answer 1

You need to use an extension, e.g. Akra-Bazzi (best version I know is Leighton's "Notes on Better Master Theorems for Divide-and-Conquer Recurrences" (https://citeseerx.ist.psu.edu/doc_view/pid/513611099c8ba4c5b8b878af143641175fe351b0). No formal reference available, sorry.

Answer 2

As said before, $T(n)$ is not linear and you cannot do that. what you can do is to prove that if $\frac{1}{a} + \frac{1}{b} \lt 1$ then $T(n) \in $ $\mathrm O (f(n))$, and this thing can be proved by induction