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:

1. Growing at a rate of $$n/3$$
2. 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$$.