1

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

slnsoumik
  • 115
  • Some times this link may be helps you. http://math.stackexchange.com/questions/890921/recurrence-relation-with-doubling-stepping-size – Bumblebee Sep 07 '14 at 18:22
  • In your last line, $(n+34) < 2n $ for $n > 34$ – user137481 Sep 07 '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. – slnsoumik Sep 07 '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)) – user137481 Sep 07 '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 –  Sep 07 '14 at 22:42

1 Answers1

2

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

You had already found everything up to the last line of that sequence of inequalities. The key is that you can continue to introduce additional multiplicative constants as long as it helps simplify your function.

David K
  • 98,388
  • aaaaah. You are right. "continue to introduce additional multiplicative constants as long as it helps simplify your function" this line made it clear for me. Thanks. I accept you answer. – slnsoumik Sep 08 '14 at 08:38
  • Beautiful. This answer looks much more intuitive than the one at http://clrs.skanev.com/04/03/06.html – arun Apr 23 '15 at 00:53