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.