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)$.

  • 3
    $\begingroup$ Showing $\dots \geq c n \log_2 n$ for some $c$ and $n \geq n_0$ is probably a more simple route here. $\endgroup$
    – Raphael
    Commented Dec 20, 2016 at 19:30
  • $\begingroup$ 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. $\endgroup$
    – AdHominem
    Commented Dec 20, 2016 at 20:02
  • $\begingroup$ The showing for some c should never be trial and error. It should be straight algebra, which by the way you have already done $\endgroup$
    – lPlant
    Commented Dec 20, 2016 at 21:55
  • $\begingroup$ 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$ $\endgroup$
    – lPlant
    Commented Dec 20, 2016 at 22:01
  • $\begingroup$ @lPlant But in that case c would be dependent on n, right? But I thought it has to be a constant? $\endgroup$
    – AdHominem
    Commented Jan 10, 2017 at 7:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.