2
$\begingroup$

The book I took this example from (Introduction to Algorithms, CLRS) wants to prove that the recurrence relation

$$T(n) = 2T(\lfloor n/2 \rfloor)+n$$

is $O(n\lg n)$ using the so-called substitution method. When proving the inductive step, they use the strong mathematical induction, so they assume that

$$\forall m : m < n, T(m) = O(m \lg m)$$

In particular, when $m=\lfloor n/2 \rfloor$ we have that

$$T(\lfloor n/2 \rfloor) \leq c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor) $$

Substituting into the recurrence yields

$$T(n) \leq 2 (c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor)) + n $$

So they multiplied by 2 both sides, but I do not understand why there's "$+n$" at the end. Of course it comes from the recurrence relation, but I don't understand why they do that. Shouldn't they just prove that $T(n) \leq c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor) $?

$\endgroup$

2 Answers 2

1
$\begingroup$

They didn't "multiply by 2 both sides". Rather, they substituted the bound they have on $T(\lfloor n/2 \rfloor)$ in the recurrence relation: \begin{align} T(n) &\stackrel{(\dagger)}= 2T(\lfloor n/2 \rfloor) + n \\ &\stackrel{(\ddagger)}\leq 2c\lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + n \end{align} Here $(\dagger)$ is the recurrence relation, and $(\ddagger)$ is the result of substituting the induction hypothesis. In order to complete the proof of the inductive step, we need to show the following inequality $(\ast)$: $$ 2c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + n \stackrel{(\ast)}\leq cn\lg n $$ In order to prove $(\ast)$, we argue as follows: $$ 2c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor \leq 2c(n/2) \lg(n/2) + n = cn(\lg n - 1) + n = cn\lg n + (c-1)n, $$ which is at most $cn\lg n$ as long as $c \geq 1$.

(For the proof to work, we also need the induction basis, which might require larger $c$. Note that the basis here is $n=2,3$, since $c1\lg 1 = 0$ is probably not a bound on $T(1)$.)

$\endgroup$
3
  • $\begingroup$ Thank you for your detailed answer and for have formatted my question better. I've got just another question: what if we did the way I asked in the question? Multiplying by 2 both sides of $T(\lfloor n/2 \rfloor) \leq c\lfloor n/2 \rfloor \lg(\lfloor n/2 \rfloor)$ and figuring out $T(n) \leq cn*lgn$. Would have that been a valid proof? $\endgroup$ Apr 26 at 8:54
  • $\begingroup$ No. If you multiply by 2, you get $2T(\lfloor n/2 \rfloor) \leq 2c\lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor$. This is not enough on its own to deduce anything about $T(n)$. You need to connect $T(n)$ to $T(\lfloor n/2 \rfloor)$ via the recurrence. $\endgroup$ Apr 26 at 8:58
  • $\begingroup$ Make sure that you understand how a proof by induction works. $\endgroup$ Apr 26 at 8:58
3
$\begingroup$

If we multiply the left-hand side $T(\lfloor n/2 \rfloor)$ by $2$, we get $2T(\lfloor n/2 \rfloor)$, not $T(n)$.

Let $P(n)$ be a propositional function. To prove that $P(n)$ is true for all $n \ge 1$, you can (sometimes) use the principle of strong induction, which states that it suffices to prove that $P(1)$ is true, and that for all $n \ge 2$, $P(n)$ is true whenever $P(1),P(2),...,P(n-1)$ is true. This assumption that each of $P(1),P(2),\ldots,P(n-1)$ is true is called the inductive hypothesis. In particular, by the inductive hypothesis, we have that $P(\lfloor n/2 \rfloor)$ is true.

In your example, $P(n)$ is the propositional function $T(n) \le c n \log n$, which you want to prove is true for all sufficiently large $n$. Of course, you can also assume that $T(n) = 2 T(\lfloor n/2 \rfloor) + n$, since you are given in the problem statement that this equation holds for all $n$. In the right hand side of this equation, there is a term $T(\lfloor n/2 \rfloor)$, for which you can substitute an upper bound of $c \lfloor n/2 \rfloor \log \lfloor n/2 \rfloor)$ because $P(\lfloor n/2 \rfloor)$ is true by the inductive hypothesis.

In other words, you can assume $T(n)=2T(\lfloor n/2 \rfloor)+n$ and $T(\lfloor n/2 \rfloor) \le c \lfloor n/2 \rfloor \log \lfloor n/2 \rfloor)$, and you try to show that $T(n) \le c n \log n$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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