Consider the recursive relation:
$$T(n)=T(an)+T((1-a)n)+cn$$
where $0<a<1$ and $c>0$ are constants(independent of $n$).Show that $T(n)=\Theta(n \lg n)$
That's what I have tried:
We suppose that $T(n)=\Theta(n \lg n)$.
So, $\exists c_1,c_2>0$ and $n_0 \geq 1$ such that $\forall n \geq n_0$:
$$c_1 n \lg n \leq T(n) \leq c_2 n \lg n$$
Suppose that the guess stands also for $an,(1-a)n$.
Then:
$$c_1 a n \lg {(an)} \leq T(an) \leq c_2 an \lg {(an)}$$
$$c_1 (1-a) n \lg {((1-a)n)} \leq T((1-a)n) \leq c_2 (1-a)n \lg {((1-a)n)}$$
Therefore:
$$T(n) \leq \lg (n) c_2 n+c_2 a n \lg( a)+c_2 (1-a)n \lg (1-a)+cn \leq c_2 n \lg n \\ \text{ if } c_2 \leq \frac{c}{\lg(1-a)-a \lg \left (\frac{a}{1-a} \right )}$$
Respectively,we show that $T(n) \geq c_1 n \lg n$.
Could you tell me if it is right?
Is there a better way to show it?