I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$
My solution:
1. Recursion tree for $T(n)=T(\frac n3)+T(\frac 2n3)+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 \rightarrow \frac 13n \rightarrow (\frac 13)^2n \rightarrow...\rightarrow 1$
- cn value on recursive tree:
Sum of each complete level is equal to cn.
- 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(cn\lg n)$
Is this solution correct? How to get rid of "c" at the end cause in task there is need for explain $\Omega(n\lg n)$ and not $\Omega(cn\lg n)$