0
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$
  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).

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Jan 20 at 16:02
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jan 20 at 16:00
  • $\begingroup$ @gorilla_glue: add $\lim_{n\to\infty}$ before my equation and you virtually have the proof. $\endgroup$
    – user16034
    Jan 20 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.