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?
Asked
Active
Viewed 47 times
1
-
I guess (otherwise provide more context) that $c$ is constant. Then $c = 2 (n−2n)$ or "c increase" is non-sense. – gammatester Jun 03 '18 at 21:42
-
c is a constant. Since $T(n)<= cnlogn - cn +cn$ evaluates to $T(n)<=cnlogn$. – trickster Jun 03 '18 at 21:49
2 Answers
1
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$$
gammatester
- 18,827
0
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.
Mike
- 20,434
-
How do i prove it. I am using induction and $T(n) <= cn lgn - cn + n$ is given to me. Logically speaking $cn lgn - cn + n$ wil decrease for all c>=1. So, We cant say that $T(n) <= cn lgn - cn + n$ holds for all c >=1. I know it does but how to prove it mathematically. – trickster Jun 03 '18 at 21:57
-
No it will not decrease, $cn \lg n$ increases w $c$, faster than $-cn$ decreases. If $T(n)$ is no larger than a certain quantity, then it is no larger than a certain quantity plus something nonnegative e.g., $cn-n$ – Mike Jun 03 '18 at 22:06