$t(n) = t(\alpha n) + t(\beta n) + cn$ , $\alpha + \beta \lt 1, c > 0$ Using tree recursion

Question

Solve $$t(n) = t(\alpha n) + t(\beta n) + cn$$ $$ \alpha + \beta \lt 1, c > 0$$

Using tree recursion

I've taken this problem when $\alpha + \beta = 1, t(n)= t(n/3) + t(2n/3) + n$

And I've got that it is $\Theta(nlogn)$

Can anyone explain how can I solve this when $\alpha + \beta < 1$ ? Maybe there's some reference in the internet already for this..

Answer 1

Building a tree:

We have to compute the work done:

$n$ - first line, root

$n/a + n / b$ - second line, children of root (sum of it $n/a + n/b$)

and like that so on..

Then we sum all the lines(because we need to sum all the work done), and we'll see that we will never exceed $n$.

So the answer is $\Theta(n)$