1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Some times this link may be helps you. math.stackexchange.com/questions/890921/… $\endgroup$
    – Bumblebee
    Sep 7 '14 at 18:22
  • $\begingroup$ In your last line, $(n+34) < 2n $ for $n > 34$ $\endgroup$
    – user137481
    Sep 7 '14 at 18:39
  • $\begingroup$ @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. $\endgroup$
    – slnsoumik
    Sep 7 '14 at 19:26
  • $\begingroup$ 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)) $\endgroup$
    – user137481
    Sep 7 '14 at 22:03
  • $\begingroup$ 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 $\endgroup$
    – user147263
    Sep 7 '14 at 22:42
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – slnsoumik
    Sep 8 '14 at 8:38
  • $\begingroup$ Beautiful. This answer looks much more intuitive than the one at clrs.skanev.com/04/03/06.html $\endgroup$
    – arun
    Apr 23 '15 at 0:53

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.