Show that solution of $T(n)=T(n-2)+2\log n$ is $O(n\log n)$

Question

I am solving this question from solution manual, but stuck at this point:

T(n)=T(n-2)+2logn
T(n)=O(nlogn)
T(n)<= c(n-2)log(n-2)+2logn
T(n)<=cnlog(n-2)-2clog(n-2)+2logn

Now I am stuck at this, how will I reduce log(n-2). So, I can get my required solution.

Answer 1

$$T(n) = T(n-2)+2 \log n$$ $$T(n) = 2 \log n + 2 \log(n-2)+ ... \text{ upto }\frac{n}{2}\text{ terms} $$ $$T(n) < 2 \log n + 2 \log n + ... \text{ upto }\frac{n}{2}\text{ terms} $$ $$T(n) < 2 (n-2) \log n < cn \log n $$

By considering half of terms from $\frac{n}{2}$ to $n$ $$T(n) > 2\log(\frac{n}{2}) + 2\log(\frac{n}{2}+2)+... \text{ upto }\frac{n}{2}\text{ terms} $$ $$T(n) > 2\log(\frac{n}{2}) + 2\log(\frac{n}{2})+... \text{ upto }\frac{n}{2}\text{ terms} $$ $$T(n) > n\log\frac{n}{2}$$ $$T(n) > n\log{n} - n \log 2$$ Since, $n\log2$ is of lower order, $$T(n) > d n \log n$$

Hence, $T(n)=\Theta(n\log n)$

Alternatively, You can use Stirling's approximation to get $\log n!=n\log n-n+ \text{O}(\log n)$

As, $$T(n)=2 \log n + 2 \log (n-2) + ... \text{ upto }\frac{n}{2}\text{ terms} $$ $$T(n) = 2 \log (2^{\frac{n}{2}}(\frac{n}{2})!)$$ $$T(n)=2 \log(2^\frac{n}{2})+2\log ((\frac{n}{2})!)$$

With Stirling's approximation, $$T(n)= n \log 2 + 2 (\frac{n}{2}\log \frac{n}{2}) - 2 \frac{n}{2} + 2 \text{ O}(\log\frac{n}{2})$$

After removing lower order terms, $$T(n)=\Theta(n\log n)$$

Answer 2

For $m\in \Bbb N$ we have $0\le 2\log m<\int_m^{m+2}\log t\, dt.$

For $3\le n\in \Bbb N$ we have $T(n)=2\log n+2\log(n-2)+...+2\log A+T(B)$ where if $n$ is odd then $A=3$ and $B=1,$ while if $n$ is even then $A=2$ and $B=0.$

In either case we have $$0\le 2\log n+2\log (n-2)+...+2\log A<\int_n^{n+2}\log t\, dt +\int_{n-2}^n \log t\, dt+...+\int_A^{A+2}\log t \,dt=$$ $$=\int_A^{n+2}\log t\, dt=$$ $$=O((n+2)\log (n+2)-(n+2))=O(n\log n)$$ because $\int \log t\, dt =t\log t -t,$ and because $\frac { (n+2)\log (n+2)-(n+2)}{n\log n}\to 1$ as $n\to \infty.$

Answer 3

Well, I can give you a simple answer as you do it in the substitution method

You got, $$T(n)\leq cn\log(n-2)-2c\log(n-2)+2\log n$$ Since, $\log (n-2) < \log n$ $$T(n) \leq cn \log n - 2 c \log (n-2) + 2 \log n$$

Since, $\log(n-2)$ and $\log n$ are of lower order than $n \log n$

$$T(n) \leq cn \log n + \text{some negligible terms compared to }n \log n$$ $$T(n) = \text{O}(n\log n)$$

But, I would not accept this as a correct answer. It's a cheat!