Recursion tree T(n) = T(n/3) + T(2n/3) + cn

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac {2n}{3})+cn$ Where c is constance, is $\Omega(n\lg n)$

My solution:

1. Recursion tree for $T(n)=T(\frac n3)+T(\frac {2n}{3})+cn$

Shortest path will be most left one, because it operates on lowest value, and the most right one will be the longest one, that means tree is not balanced.

Shortest path can be define as: $n -> \frac 13n -> (\frac 13)^2n ->...->1$

2. cn value on recursive tree:

Sum of each complete level is equal to cn.

3. Elements from shortest path are being divided by 3, so length of this path will be equal to $\log_3n$. So if number of complete levels of recursion tree for shortest path is equal to $\log_3n$, that means cost of algorithm for this path will be: $T(n)=cn\log_3n=\Omega(n\lg n)$

In Big Omega notation we can skip base of logarithm and constant factors.

Is this solution correct, am I missing something?

Yes, your understanding and your answer are correct. If you'd like a more in-depth analysis of what's going on with this recurrence relation, recall the definition of a binomial coefficient $$(x+y)^k=\sum_{i=0}^k\binom ki x^{k-i}y^i$$

Now take another look at the recursion tree written without the simplifications you used

Notice that there is a pattern emerging with the coefficients to $cn$ at each level. They are the binomial coefficients with $x = \frac{1}{3}$ and $y = \frac{2}{3}$. Here are the first few levels written out more explicitly

Thus the summation of work done by the nodes for each level is \begin{align*} \text{Level } 0&: cn = \left( \frac{1}{3} + \frac{2}{3} \right)^0cn\\ \text{Level } 1&: \left(\frac{1}{3}\right)^1\left(\frac{2}{3}\right)^0cn + \left(\frac{1}{3}\right)^0\left(\frac{2}{3}\right)^1cn = \left( \frac{1}{3} + \frac{2}{3} \right)^1cn\\ \text{Level } 2&: \sum_{i=0}^2\binom 2i \left(\frac{1}{3}\right)^{2-i}\left(\frac{2}{3}\right)^i = \left( \frac{1}{3} + \frac{2}{3} \right)^2cn\\ & \vdots \\ \text{Level } k&: \sum_{i=0}^k\binom ki \left(\frac{1}{3}\right)^{k-i}\left(\frac{2}{3}\right)^i = \left( \frac{1}{3} + \frac{2}{3} \right)^kcn\\ \end{align*}

Also notice that the sum of work across the nodes on each individual level up to this point is $(1)\cdot cn = cn$ and if there are $k$ levels so far, the total work done up to this point is $cn \cdot k$. However, since the right subtree is doing more work than the left subtree ($\frac{2n}{3} > \frac{n}{3}$), we will eventually see that its leaf nodes (i.e., base cases) appear at a lower level in the tree and leaf nodes across the tree will be staggered.

The next step is to argue a lower bound on the height of the tree. The leftmost leaf on the left subtree will be at height $h_{left} = \text{log}_3(n)$ and the rightmost leaf on the right subtree will be at height $h_{right} = \text{log}_{3/2}(n)$. This is based on the binomial coefficients at those locations, with $\left(\frac{1}{3}\right)^k\left(\frac{2}{3}\right)^0 = \left(\frac{1}{3}\right)^k$ at the leftmost leaf and $\left(\frac{1}{3}\right)^0\left(\frac{2}{3}\right)^k = \left(\frac{2}{3}\right)^k$ at the rightmost leaf. So $k = h_{left}$ occurs when $n = \left(\frac{1}{3}\right)^k \Rightarrow k = \log_3(n)$ and $k = h_{right}$ occurs when $n = \left(\frac{2}{3}\right)^k \Rightarrow k = \log_{3/2}(n)$.

Since we are looking for a lower bound, we will use $h_{left} = \text{log}_3(n)$. Consider a full complete binary tree with height $2^{\text{log}_3(n)}$ formed by taking our recurrence tree and cutting off all nodes on the right past this level and converting the remaining nodes at this last level into leaf nodes. Clearly, this gives a lower bound since we have excluded the higher-level staggered nodes on the right subtree. Thus (assuming a value of $T_1$ at the leaf level) a lower bound for $T(n)$ is given by \begin{align*} T(n) &\ge (\text{work done by leftmost leaves}) + (cn \cdot h_{left}) \\ T(n) &\ge T_1 \cdot 2^{\text{log}_3(n)} + cn\cdot\text{log}_3(n) \\ &= T_1 \cdot n^{\text{log}_3(2)} + cn\cdot\text{log}_3(n) && \text{by properties of logarithms}\\ &\approx T_1 \cdot n^{1.6} + cn\cdot\text{log}_3(n) \\ &= \Omega(n\text{lg}n) \end{align*}