Prove that $O((N+1)\log(N+1)) \approx O(N\log N)$

Question

I am trying to prove that $O((N+1)\log(N+1)) \approx O(N\log N)$. I have the following:

Assume that $N \geq 1$. Then: \begin{align} N+1 &\leq N + N \leq 2N \\ \log(N+1) &\leq \log(2N) = \log 2 + \log N \\ \log(N+1) - \log2 &\leq \log N \end{align} However, I am not exactly sure how to continue from here. What techniques could I use to demonstrate that $O((N+1)\log(N+1)) \approx O(N\log N)$? I am thinking that one way to prove this is to show that $N\log N$ can be larger than $(N+1)\log(N+1)$ under certain circumstances. Any insights are appreciated.

Answer 1

First, show that $N^2>N+1$ for $N$ big enough (how big?) and second, $2N>N+1$ for $N$ big enough (this, you have already). This implies, that for any constant $c_1\in \mathbb R_+$, and for $N$ big enough

\begin{align}c_1(N+1)\log {(N+1)}\le c_12N\log{N^2}=c_14N\log{N}=\mathcal O(N\log{N})\end{align}

Answer 2

If we have some: $$f(n)=n\log(n)$$ and: $$f(n+1)=(n+1)\log(n+1)$$ we can see that when $n\to\infty$ the value of $1$ compared to $n$ is small enough that: $$O(n)=O(n+1)$$ and we can continue this to say that: $$O[f(n)]=O[f(n+1)]$$ Hence: $$O[n\log(n)]=O[(n+1)\log(n+1)]$$