Complexities of Recurrences in the form $t(n) = t(\alpha n) + t(\beta n) + cn$

33 Views Asked by At

When considering recurrence relations, they are generally of a form similar to

$$t(n) = t(\alpha n) + t(\beta n) + cn$$

and there are three cases to be considered for our values of $\alpha$ and $\beta$, being

$$\alpha + \beta < 1$$ $$\alpha + \beta = 1$$ $$\alpha + \beta > 1$$

We are able to show that for our first case, we receive $t(n) = O(n)$, and in our second case $t(n) = O(nlog n)$, but are we able to analyze the big-Oh for the third case? I know we can consider the third case to be $t(n) = \Omega(nlogn)$ but is it possible to draw any further conclusion?