Need help figuring out substitution with recurrence equation.

Question

I need help with an Algorithm text book problem. The problem is the following

T(n) = 2T(n/2) + n

We guess that the solution is T (n) = O(n lg n). Our method is to prove that T (n) ≤ cn lg n for an appropriate choice of the constant c > 0. We start by assuming that this bound holds for ⌊n/2⌋, that is, that T (⌊n/2⌋) ≤ c ⌊n/2⌋ lg(⌊n/2⌋). Substituting into the recurrence yields.

This is the answer that is given.

   T(n) ≤ 2(c ⌊n/2⌋lg(⌊n/2⌋)) + n  Step 1
   ≤ cn lg(n/2) + n                Step 2
   = cn lg n - cn lg 2 + n         Step 3
   = cn lg n - cn + n              Step 4
   ≤ cn lg n,                      Step 5

However, there is a couple steps that confuses me.

In step 2 shouldn't lg(n/2) be lg n since we should multiply it by 2?

In step 3 I am completely confuse on why we subtract cn lg 2 + n from cn lg n

Any tips or suggestions are appreciated. I am trying to learn this on my own, but I need someone to guide me on this.

Answer 1

In general, if you want to prove that a given function is the solution of a recurrence relation you will need the following relations:

$$x-1< \lfloor x \rfloor \leq x \leq \lceil x \rceil < x+1$$

$$\lg \left( \frac{a}{b}\right)= \lg a- \lg b$$

Also, I would suggest you to take a look at the Master Theorem with which you can easily find the solution of a recurrence relation.

Answer 2

Step 2: $$2 c \lfloor n/2 \rfloor \operatorname{lg} \lfloor n/2 \rfloor \le 2 c (n/2) \operatorname{lg} (n/2)=2cn \operatorname{lg}(n/2)$$

Step 3 (property of logarithm): $$\operatorname{lg}(n/2) = \operatorname{lg}(n)-\operatorname{lg}(2)$$