$T(n) \le cn\lg n-cn+n\le cn\log n$ for $c \geq 1$

Question

I am confused with respect to this equality. For $c>=1$, $(n-cn)$ should be less and less. For example if $c = 2, then (n-cn)$ should be $-n$ and overall equality changes to $T(n)<= nlogn - n$. And thus $cn\log n-cn+n$ should decrease for larger value of $c$ and the <= should not hold, as $cn\log n-cn+n$ decreases as $c$ increase. I know for a fact that this is correct, so where am I wrong?

Answer 1

By the way, your question is rather confusingly written. For $c>1$

$T(n) \le cn \lg n -cn+n \le cn \lg n$ holds for all $n$.

Meanwhile $cn \lg n$ increases faster than $-cn$ decreases (for large $n$). And as $n$ tends to infinity, $cn \lg n$ increases (with $c$) much faster than $-cn$ decreases.

The $cn \lg n$ term dominates the $cn$, $n$ terms.

Answer 2

Since $c\ge 1$ you have $1-c \le 0$ and therefore $$cn\lg n - cn+n = cn \lg n + n(1-c) \le cn \lg n$$