Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution I have to solve this using the substitution method. 

Floor functions cannot be skipped.



IH: Assume that $T(k) \geq  ck\log(k) $ for all $k \leq n$, where c is a constant.

IS: Must prove $T(k) \geq  ck\log(k) $

Proof:

\begin{align*}
T(n) &amp;= 2T(\left \lfloor{k/2}\right \rfloor ) + k\\
     &amp;\geq 2 c\left \lfloor{k/2}\right \rfloor\log(\left \lfloor{k/2}\right \rfloor) +k
\end{align*}

We now have two cases: $k$ is even and $k$ is odd. It is easy to prove this case when $k$ is even, however I run into trouble when $k$ is odd.

When k is odd, $\lfloor k/2\rfloor = (k-1)/2$, which gives

\begin{align*}
T(n)&amp;\geq 2 c\tfrac{k-1}2\log(\tfrac{k-1}2) +k\\
&amp;=  c(k-1)\big(\log(k-1)-1\big) +k \qquad\qquad\text{(Since $\log2 = 1$)}\\
&amp;=  c\big(k\log (k-1) - k -\log(k-1) + 1\big) +k\\
&amp;=  ck\log (k-1) - ck -c\log(k-1) + c +k\\
&amp;=  ck\log k  + ck\log\big(1-\tfrac{1}k\big) - ck -c\log(k-1) + c +k\,,
\end{align*}
where the last equality is because $\log(a-b) = \log\big(a\big(1-\tfrac{b}a\big)\big)$.

And here is where I am stuck. I have gotten the $ck\log k$, but cannot find the $c$ that will let me finish the problem. 

Any help would be appreciated.
One way to go around the difficulties is as follows.

First, you prove that $T(n) = \Omega(n \log n)$ when $n = 2^k$.

Second, you prove that $T(n)$ is monotone (given monotone base cases).

Third, you finish the proof as follows. Let $m \leq n &lt; 2m$, where $m = 2^k$. Then
$$
 T(n) \geq T(m) = \Omega(m \log m) = \Omega(n \log n).
$$
Details left to you.