# Dropping terms in proving the runtime for a recurrence?

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)?

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).

• Thanks for your answer! Do you have an example of a proof for showing the runtime is $\Theta(\cdot)$ by any chance so I could see how others usually go about proving it? Jan 20 at 16:02

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.

• I was actually thinking about this, but I felt hesitant to ignore "slower growing" terms like g(n) in an inequality. Do you have any examples/sources where this is explicitly acknowledged or shown in a proof by any chance? Jan 20 at 16:00
• @gorilla_glue: add $\lim_{n\to\infty}$ before my equation and you virtually have the proof.
– user16034
Jan 20 at 16:02