How do you prove the following?
$$f(N)=N\space lg\space N + O(N) \implies f(N) = \Theta(N \space log \space N)$$
Here $lg\space N \equiv log_2\space N$, and $O$ stands for the big-O, and $\Theta$ stands for big-theta. And $log \space N \equiv log_e \space N$, i.e. natural logarithm
My reasoning may not be all that mathematically pleasing (or even correct)...but here goes...
We have $f(N)=N\space lg\space N + O(N)$
By definition, $O(f(N))$ stands for the some upper bound for the function $f(N)$.
Therefore, in our relation $O(N)$ (being an upper bound function) should theoretically contain $f(N)$ as $N \rightarrow \infty$.
Now consider the lower bound of $f(N)$ to be some function of $N \space lg \space N$, i.e. $\Omega(f(N)) \equiv f(N \space lg \space N)$
Now, $lg \space N \equiv log_2 \space N > log \space N$, where $log$ stands for natural logarithm. Hence natural logarithm is some constant factor of "binary" logarithm, where that constant is less than 1.
So all the above reasoning naturally implies our above assertion, right? Where am I wrong?