Argue that the solution to the recurrence \(T(n) = T(n/3) + T(2n/3) + cn\), where c is a constant, is \(\Omega(n \lg n)\) by appealing to a recursion tree.
The recurrence has two branches:
- Growing at a rate of \(n/3\)
- Growing at a rate of \(2n/3\)
The lower bound (\(\Omega\)) will be determined by the branch that terminates faster, as asymptotically the running time cannot be slower than that.
In this case, the branch of \(T(n/3)\) will terminate, or reach leaf nodes, faster than the other one.
Recursion Tree for Ω
At depth \(i = 0, 1, 2, \dots, \log_3 n\) of the tree, there are some nodes that costs a total of \(cn\).
Hence, total cost of the tree is:
\[\begin {aligned} T(n) & = \sum_{i = 0}^{\log_3 n} cn \\ & = (\log_3 n + 1) cn \\ & = cn \log_3 n + cn \\ & = \frac{cn \log n}{\log 3} + cn\\ & \ge cn \log n \\ & = \Omega(n\log n) \end {aligned}\]The last step holds as long as \(cn \ge \log 3\).