# The solution of recurrence $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$ is $O(n\lg n)$

Given, $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$. Show that the solution to T(n) is $O(n\lg(n))$.

Here's what I tried -

Assumption: $T(\lfloor n/2 \rfloor) \le c(\lfloor n/2\rfloor + 17)\cdot \lg(\lfloor n/2 \rfloor + 17)$ for some constant $c$ and for some $n \ge n_0$

Inductive step:

$$\begin{split} T(n) &\le 2c(\lfloor n/2\rfloor + 17) \lg(\lfloor n/2\rfloor + 17) + n \\ & \le 2 c (n/2 + 17)\lg(n/2 + 17) + n \\ & \le c (n + 34) \lg((n+34)/2) + n \\ & = c(n+34)\lg(n+34) - cn - 34c + n \\ & \le c (n + 34)\lg(n + 34) \quad \text{(for c \ge 1)} \end{split}$$

So I am stuck here... how do I 'remove' the $34$s from this inequality? (This is exercise 4.3-6 of CLRS)

(Thanks @user137481)

The above reduces to $T(n) <= cn.lg(n) + cn$ which is not quite $O(nlg(n))$. As described in CLRS, in such situations even if the inductive hypothesis is correct, we may not be able to arrive at the exact form. In this case we are offset by a lower order term $cn$ needs to be removed. So the new guess is $T(n) <= cnlg(n) - dn$, (this is still,of course, $O(nlg(n)$). Now,

$T(n) \le 2.c.(\lfloor n/2\rfloor + 17).lg(\lfloor n/2\rfloor + 17) - 2dn + n$

$\le 2.c.(n/2 + 17).lg(n/2 + 17) -2dn + n$

$= c(n+34).lg(n+34) - c(n+34) - 2dn + n$

$\le 2cn.lg(2n)-2cn-2dn+n\;$ (for $n>=34$)

$=cn.lg(n) - cn + dn +n\;$ (absorbing 2 into c)

$\le cn.lg(n)\;$ (for all $c - d \ge 1$)

Therefore, $T(n) = O(n.lg(n))$

(This is what I have done, if there is any mistake, please correct me, if not, I will rewrite this as an answer and accept it).

• Some times this link may be helps you. math.stackexchange.com/questions/890921/… Sep 7 '14 at 18:22
• In your last line, $(n+34) < 2n$ for $n > 34$ Sep 7 '14 at 18:39
• @user137481 ah.. yes. So that can be said for lg(n+34) too. Which brings it to T(n) <= cn.lg(n) + cn (for some c >= 1 and n >= 34) (...just absorbing the 2 into the constant c). As mentioned in CLRS, I need to subtract a lower order term, in this case (d.n) in order to prove the exact form of the induction. Sep 7 '14 at 19:26
• It does not need to be so complicated. Recall that if $f(n) = an^2+bn+c$ we have $f(n) = O(n^2)$ because we just keep the largest term and drop constants. Similarly, if $f(n)=cn.lg(n) + cn$, for n > 2, cn.lg(n) > cn. So, the largest term is cn.lg(n)which is O(nlg(n)) Sep 7 '14 at 22:03
• I reformatted the first half of the post, leaving the second part to you. For example, \lg n is the way to write $\lg n$. And those dots are not necessary: implied multiplication is understood. If you really think they are necessary, use \cdot to make the dot centered. Also see MathJax tutorial
– user147263
Sep 7 '14 at 22:42

As noted in the comments, when computing the "big-O" asymptotic form of a function, you can impose any lower bounds on the input $n$ that you like (for example, require $n > 34$). And you know that you can multiply an expression by a constant factor without changing its "big-O" form.
Once you have found that $T(n) \le c\cdot(n+34)\cdot\lg(n+34),$ then you can conclude, for $n > 34,$
$$\begin{eqnarray} T(n) &\le& c\cdot(n+34)\cdot\lg(n+34) \\ &\le& c\cdot(2n)\cdot\lg(2n) \\ &\le& 2cn\cdot(1 + \lg n) \\ &\le& 2cn\cdot(2 \lg n) = 4c\cdot(n \lg n) = O(n \lg n). \\ \end{eqnarray}$$