# Solving $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ with substitution method

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

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

• 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? Apr 26 at 8:54
• 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. Apr 26 at 8:58
• Make sure that you understand how a proof by induction works. Apr 26 at 8:58

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