Lower bound for Merge Sort running time I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log_2 n)$.

Here's my attempt: Suppose there is some $c&gt;0$ and a positive integer $n_0$ such that $n_0 \le k &lt; n \implies T(k) \ge ck \log_2 k$. 

Then

$$\begin{eqnarray*}
T(n) &amp;=&amp; 2T(\left \lfloor \frac{n}{2} \right \rfloor) + n \\
&amp;\ge&amp; 2c \left \lfloor \frac{n}{2} \right \rfloor \log_2 \left \lfloor \frac{n}{2} \right \rfloor + n \\
&amp;\ge&amp; 2c \left ( \frac{n - 1}{2} \right ) \log_2 \left ( \frac{n - 1}{2} \right ) + n \\
&amp;=&amp; c(n - 1) \log_2(n - 1) - c(n - 1) + n \\
&amp;=&amp; cn \log_2(n-1) - c \log_2(n-1) - c(n - 1) + n \\
&amp;=&amp; cn \log_2 \left [ n \left ( 1 - \frac{1}{n} \right ) \right ] - c \log_2(n-1) - c(n - 1) + n \\
&amp;=&amp; cn \log_2 n + cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n.
\end{eqnarray*}$$

I can't determine if there is a $c &gt; 0$ such that $cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$ is non-negative for $n$ large enough.

Also, I think this approach is too complicated given how easy it is to prove $T(n)=O(n \log_2 n)$. Am I missing some obvious estimate here?

Any help is welcome. Thanks.
$c=\frac{1}{2}$ is enough for large enough $n$.

Indeed, there are positive integers $n_1$ and $n_2$ such that 

$$\begin{eqnarray*}
n &amp;\ge&amp; n_1 \implies -\frac{1}{2} &lt; \log_2 \left ( 1 - \frac{1}{n} \right ) \\
n &amp;\ge&amp; n_2 \implies -\frac{1}{2} &lt; -\frac{1}{n} \log_2 (n - 1).
\end{eqnarray*}$$

Rewriting $$cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$$

as 

$$
cn \left [ \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c} \right ],
$$

we have

$$n \ge \max(n_1, n_2) \implies -2 + \frac{1}{c} &lt; \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c}.$$

But $-2 + \frac{1}{c} \ge 0 \iff c \le \frac{1}{2}$.