# Proof that $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$ (lower bound of sorting algorithms)

Regarding the last step of the proof of the lower bound of comparison based sorting, there is the following implication for the runtime T in my book:

$T \ge n \log_2 n - n \log_2 e \implies T \in \Omega(n \log_2 n)$

I tried to verify this by proof, is my conclusion correct?

For any real value $x, a$ element of the extended real numbers:

$f \in \Omega(g) \implies \liminf_{x \rightarrow a} \Big \lvert \frac{f(x)}{g(x)} \Big \rvert > 0$

For $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$ it has to be shown that $a$ exists so that $\liminf_{x \rightarrow a} \bigg \lvert \frac{n \log_2 n - n \log_2 e}{n \log_2 n} \bigg \rvert$ is positive. Since $\bigg \lvert \frac{n \log_2 n - n \log_2 e}{n \log_2 n} \bigg \rvert = \bigg \lvert 1 - \frac{1}{\ln n} \bigg \rvert$, the above limes inferior will be 1 for $a = \infty$.

It follows that $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$.

• Showing $\dots \geq c n \log_2 n$ for some $c$ and $n \geq n_0$ is probably a more simple route here. Commented Dec 20, 2016 at 19:30
• I know, I just think using this definition is less of a trial and error approach, also in this representation the limes notation makes it more obvious that this is about asymptotics. I know I could probably just use $n_0 = 5, c = 0.1$ and be fine, thats why I asked if this approach is correct as well. Commented Dec 20, 2016 at 20:02
• The showing for some c should never be trial and error. It should be straight algebra, which by the way you have already done Commented Dec 20, 2016 at 21:55
• From what you have already shown: $n \log_2 n - n \log_2 e \geq cn \log_2 n$ so $\frac{n \log_2 n - n \log_2 e}{n \log_2 n} = 1 - \frac{1}{\ln n} \geq c$ and then $1 - \frac{1}{\ln n} \geq c$ so for arbitrarily $n_0>2$ we can always find a $c$ value since $1 - \frac{1}{\ln n} > 0$ Commented Dec 20, 2016 at 22:01
• @lPlant But in that case c would be dependent on n, right? But I thought it has to be a constant? Commented Jan 10, 2017 at 7:50