Use a recursion tree to give an asymptotically tight solution to the recurrence $$T(n) = T(\alpha n) + T((1 - \alpha)n) + cn$$, where $$\alpha$$ is a constant in the range $$0 < \alpha < 1$$ and $$c > 0$$ is also a constant.

Frankly speaking, solving it the “proper” way is way too mathematical and I don’t enjoy writing solutions for such problems.

Intuitively if you think about it, we are subdividing the problems in two parts, $$\alpha n$$ and $$(1 - \alpha)n$$, and in each stage we are having total cost of $$cn$$. Depending upon which branch of subproblem is longer than the other, we’ll have a maximum of either $$\log_{1/\alpha} n$$ or $$\log_{1/(1 - \alpha)} n$$ levels.

For example, merge sort has exactly same recurrence with $$\alpha = 1/2$$. And we already know the solution to that is $$\Theta(n \lg n)$$. And that can be a good guess for this problem as well.