Solving T(n) = O(n lg n) using substitution method?

[evinda]

Hello! :-)

I am looking at the following exercise:
Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$.

So,we suppose that $T(n)=O(n \lg n)$.

In order the recursive relation to be well-defined,I thought to use the inequality $\lfloor x \rfloor \geq x-1$ and I found:

$$ \lfloor \frac{n}{2} \rfloor+17 \leq n \Rightarrow n \geq \lfloor \frac{n}{2} \rfloor +17> \frac{n}{2}-1+17 \Rightarrow n>\frac{n}{2}+16 \Rightarrow n\geq 33$$

$$\text{ So, } n_0=33$$

As $T(n)=O(n \lg n)$,we suppose that $\exists c,b>0 \text{ such that } \forall n \geq 33 : T(n) \leq c(n-b) \lg n$We suppose that the relation stands also for $\lfloor \frac{n}{2} \rfloor+17$,then: $T(\lfloor{\frac{n}{2}} \rfloor+17) \leq c(\lfloor \frac{n}{2} \rfloor +17-b) \lg (\lfloor \frac{n}{2} \rfloor+17)$

$$T(n)\leq 2c(\lfloor \frac{n}{2} \rfloor+17-b) \lg ( \lfloor \frac{n}{2} \rfloor +17)+n \leq 2c (\frac{n}{2}+17-b) \lg n+n = c(n-b+(34-b)) \lg n +n \leq c(n-b) \lg n +n,\text{ if } 34 \leq b$$

We also know that it must be $ T(n)\geq 0 \Rightarrow n \geq b \Rightarrow b\leq n, \forall n \geq n_0 \Rightarrow b\leq n_0 \Rightarrow b \leq 33$

So,we have a contradiction..Also,even if it was not a contadiction,we couldn't do it in this way,because: $c(n-b) \lg n +n \geq c(n-b) \lg n$

But..how can we show it then? (Thinking)

 

[Evgeny.Makarov]

I am looking at the following exercise:
Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$.

So,we suppose that $T(n)=O(n \lg n)$.

Do you always assume what you need to show?

As $T(n)=O(n \lg n)$,we suppose that $\exists c,b>0 \text{ such that } \forall n \geq 33 : T(n) \leq c(n-b) \lg n$

Why not $T(n) \leq cn\lg n$?

This problem would be covered by the master theorem (case 2) if it were not for $+17$. It is covered by the Akra–Bazzi method, which is a generalization of the master theorem. In the notations of the Wiki page, $g(x)=x$, $k=1$, $a=2$, $b=1/2$ and $h(x)=17+\lfloor n/2\rfloor-n/2$. However, this theorem is more advanced and may not be covered in some courses dealing with recurrence relations.

What is the context of this problem? Where in the course or book are you? What methods are you supposed to solve it?

 

[evinda]

Do you always assume what you need to show?

I saw at the solution of a similar exercise that they did it like that.. So is it wrong? (Thinking)(Worried)

Why not $T(n) \leq cn\lg n$?

I have also tried it,supposing $T(n) \leq cn\lg n$,then I supposed that the relation also stands for $\lfloor \frac{n}{2} \rfloor +17: T(\frac{n}{2} \rfloor +17) \leq c( \lfloor \frac{n}{2} \rfloor +17) \lg (\lfloor \frac{n}{2} \rfloor+17)$

So:

$$T(n) \leq 2c(\lfloor \frac{n}{2} \rfloor+17) \lg (\lfloor \frac{n}{2} \rfloor+17)+n \leq 2c(\lfloor \frac{n}{2} \rfloor+17) \lg n+n \leq 2c(\frac{n}{2}+17) \lg n+n \leq c(n+34) \lg n +n$$

This problem would be covered by the master theorem (case 2) if it were not for $+17$. It is covered by the Akra–Bazzi method, which is a generalization of the master theorem. In the notations of the Wiki page, $g(x)=x$, $k=1$, $a=2$, $b=1/2$ and $h(x)=17+\lfloor n/2\rfloor-n/2$. However, this theorem is more advanced and may not be covered in some courses dealing with recurrence relations.

What is the context of this problem? Where in the course or book are you? What methods are you supposed to solve it?

I haven't seen the Master theorem yet..I am supposed to solve it,using the substitution method.. (Worried)