# 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>0$$ and a positive integer $$n_0$$ such that $$n_0 \le k < n \implies T(k) \ge ck \log_2 k$$.

Then

$$\begin{eqnarray*} T(n) &=& 2T(\left \lfloor \frac{n}{2} \right \rfloor) + n \\ &\ge& 2c \left \lfloor \frac{n}{2} \right \rfloor \log_2 \left \lfloor \frac{n}{2} \right \rfloor + n \\ &\ge& 2c \left ( \frac{n - 1}{2} \right ) \log_2 \left ( \frac{n - 1}{2} \right ) + n \\ &=& c(n - 1) \log_2(n - 1) - c(n - 1) + n \\ &=& cn \log_2(n-1) - c \log_2(n-1) - c(n - 1) + n \\ &=& cn \log_2 \left [ n \left ( 1 - \frac{1}{n} \right ) \right ] - c \log_2(n-1) - c(n - 1) + n \\ &=& 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 > 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.

• "Suppose there is some $c>0$ and a positive integer $n_0$ such that $n_0 \le k < n \implies T(k) \ge ck \log_2 k$." What is $n$ here? – xskxzr Feb 22 at 2:49
• It's a positive integer for which I want to prove(by induction) the bound $T(n) \ge cn \log_2 n$. – lzralbu Feb 22 at 4:14

$$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 &\ge& n_1 \implies -\frac{1}{2} < \log_2 \left ( 1 - \frac{1}{n} \right ) \\ n &\ge& n_2 \implies -\frac{1}{2} < -\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} < \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}$$.