Dropping terms in proving the runtime for a recurrence?

Question

I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this:

Recurrence: $T(1)=1$ and $T(n)=2 T(\lfloor n / 2\rfloor)+n$ for $n>1$. We guess that the solution is $T(n)=O(n \log n)$. So we must prove that $T(n) \leq c n \log n$ for some constant $c$. (We will get to $n_0$ later, but for now let's try to prove the statement for all $n \geq 1$.)

As our inductive hypothesis, we assume $T(n) \leq c n \log n$ for all positive numbers less than $n$. Therefore, $T(\lfloor n / 2\rfloor) \leq c\lfloor n / 2\rfloor \log (\lfloor n / 2\rfloor))$, and

$$ \begin{aligned} T(n) & \leq 2(c\lfloor n / 2\rfloor \log (\lfloor n / 2\rfloor))+n \\ & \leq c n \log (n / 2)+n \\ & =c n \log n-c n \log 2+n \\ & =c n \log n-c n+n \\ & \leq c n \log n \quad(\text { for } c \geq 1) \end{aligned} $$

I have two questions:

1. In the last step, the author omits the $-cn$ and $n$ terms, and I think they did this because setting a bound for $c$ makes these terms irrelevant. Is this correct? If so, I was hoping someone could spell out why these terms can be removed :).

2. Could something similar be done for proving $\Theta(\cdot)$ (i.e. a lower and upper bound)?

Answer 1

1. In the last step, there is an inequality. Since it is assumed that $c\geqslant 1$, then $-cn + n = (1 - c) n \leqslant 0$, so the inequality is correct, it is not a matter of irrelevance or not.

2. For $\Theta$, it would be better to prove two different inequalities by induction, with different coefficients (however, the proof could be similar).

Answer 2

For 1. (though Nathaniel answered for the case in question) generally, in $f(n)+g(n)$ where $g(n)=o(f(n))$, you can drop the term $g(x)$ because it becomes negligible.

$$f(n)+g(n)=f(n)\left(1+\frac{g(n)}{f(n)}\right)=f(n)(1+\epsilon(n))$$ where the function $\epsilon$ tends to zero and the factor on the right can be bounded by a constant.