-1

So I need to prove that T(n) is $O(n\text{log}(n))$, considering $c>0$ is a constant and using substitution method

What I've tried so far:

We need to prove that $T(n) \leq dn\text{log}(n), d\geq0$

Assuming that $T(\frac{n}{2}) \leq dn\text{ln}(\frac{n}{2})$, we have

$T(n) \leq dn\text{ln}(\lfloor{\frac{n}{2}}\rfloor) + dn\text{ln}(\lceil{\frac{n}{2}}\rceil) + 1$

Removing the ceil and the floor, I'm guessing we don't want to equal both of them to $\frac{n}{2}$, so

$T(n) \leq dn\text{ln}(\frac{n}{2}) + dn\text{ln}(\frac{n+1}{2}) + 1$

$T(n) \leq dn\text{ln}(n)-dn\text{ln}(2) + dn\text{ln}(n+1) - dn\text{ln}(2)+1$

$T(n) \leq dn\ln(n) + dn\ln(n+1) -2dn + 1$

And I have no idea how to continue this.

Moni145
  • 2,142
edwardsols
  • 1

1 Answers1

1

By strong induction, $T$ is a growing function. Indeed,

$$T(2)=2T(1)+c>T(1)$$ and $$T(n+1)=T\left(\left\lfloor\dfrac{n+1}2\right\rfloor\right)+T\left(\left\lceil\dfrac{n+1}2\right\rceil\right)+c(n+1)>T(n).$$

Now if we take $n:=2^k$,

$$T(2^k)=2T(2^{k-1})+c\,2^k,$$ which can be written

$$S(k)=2S(k-1)+c\,2^k.$$

Using the theory of linear recurrences, we know that the solution will be of the form

$$S(k)=(ak+b)2^k$$ and by identification,

$$(ak+b)2^k=2(ak-a+b)2^{k-1}+c\,2^k,$$

$a=c$ and $b$ is free. Hence

$$S(k)=(ck+S(0))2^k$$ and

$$T(n)=(c\log_2(n)+T(1))n.$$

As the function is monotonous, this justifies the $O(n)$ bound, and even $\Theta(n)$.

Below, the exact curve of $\dfrac{T(n)}n$ for $c=1,T(1)=0$.

enter image description here

In fact, though you can't see it on this plot, the growth is perfectly linear between two powers of $2$.