0

I'm looking for an easy way to prove that $((n+1)*\log_2(n+1)-n) = \Theta(n*\log(n))$.

I've used the limit definition of $\mathcal{O}$ with L'Hôpital's rule on this, but I find this rather exhaustive. Is there an easier way to do this?

Thanks for any help.

3nondatur
  • 4,178

2 Answers2

1

We can apply the definition $$\limsup_{n} \frac{(n+1)\log_2(n+1)-n}{n\log(n)} = \limsup_n \frac{n(\log_2(n+1)-1)+\log_2(n+1)}{n\log(n)} = \leq \limsup_n \frac{n(\log_2(n+1)-1)}{n\log(n)} + \limsup_n \frac{\log_2(n+1)}{n\log(n)}. $$ The last limit is clearly zero, so after simplifying $n$ on the left ratio we get $$ \limsup_n \frac{\log_2(n+1)-1}{\log(n)} \leq \limsup_n \frac{\log(n+1)}{\log(n)\ln(2)} + \limsup_n \frac{-1}{n\log(n)} = \frac{1}{\ln(2)}. $$ If you pass though the computation you can see that $\limsup$ can be turned into a $\lim$ and all inequalities into equalities, so that the estimate is optimal.

Tommaso Seneci
  • 1,499
1

Find $\lim_{n}\frac{f(n)}{g(n)}$, where f and g are the involved functions in your post. If this limit is a positive constant, then result follows from the definition of "O".

user123043
  • 154