solve recursion $T(n) = T(\alpha n)+T(\beta n)+\gamma n$

Question

I need solve this recursion: $$T(n) = T(\alpha n)+T(\beta n)+\gamma n$$ I know that for $\alpha +\beta< 1$ solution is $O(n)$

How is for $\alpha + \beta = 1$ and $\alpha + \beta > 1$?

Answer 1

Take a look at Leighton's "Notes on Better Master Theorems for Divide-and-Conquer Recurrences" (1996).

Answer 2

Normally if you suspect something you should simply substitute it $T(n)=knG(n)$. So we have

$$knG(n)=kn\alpha G(\alpha n)+kn\beta G(\beta n) + \gamma n$$

and this gives

$$G(n)=\alpha G(\alpha n)+\beta G(\beta n) + \frac{\gamma}{k}$$

This recursion cannot have any other solution than constant (if it is to have any solution at all) $G(n)=c$ and it is even strict what constant it must be

$$c=\frac{\gamma}{k(1-\alpha-\beta)}$$

If $\alpha + \beta = 1$ then it must be $\gamma = 0$ if we want to have at least one solution.

So the solution is

$$ T(n)=n\frac{\gamma}{1-\alpha-\beta}, \; \alpha+\beta \neq 1 $$ $$ T(n)=kn, \; \alpha+\beta = 1, \; \gamma = 0 $$

This makes it $O(n)$ whatever it takes but you cannot neglect restrictions, if you want to have any solution, and in the case $\alpha+\beta = 1$ although still linear $k$ can be as large as you like. Similar if $\alpha+\beta$ is very close to 1.