I have a task and have just a little problem with it, but I cannot find answer.
Explain that by using recursion tree that solution for: T(n)=T(n/3)+T(2n/3)+cn Where c is constance, is Omega(n lg n)
My solution: 1. Recursion tree for T(n)=T(n/3)+T(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 -> 1/3 n -> (1/3)^2 n ->...->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_3 n. So if number of complete levels of recursion tree for shortest path is equal to log_3 n, that means cost of algorithm for this path will be: T(n)=cn log_3 n=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). I thought that big Omega notation will help and I can just ignore "c", but my teacher said that "constant according to definition [I don't know which definition] is important"