Let $T(1)=1$, $T(n)=2T(\lfloor\frac{n}{2}\rfloor)+n$; show that $T \in \mathcal{O}(n\log(n))$.
I have expanded $T(n)$ in the following terms:
\begin{align} T(n) &= 2T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n \\ &=2\left(2T\left(\left\lfloor\frac 12 \left\lfloor\dfrac{n}{2}\right\rfloor\right\rfloor\right)+\left\lfloor\frac{n}{2}\right\rfloor\right)+n \\ &=\ldots \\ &=2^{\lfloor \log_{2} (n)\rfloor}T(1)+ n+ 2\left\lfloor\frac{n}{2}\right\rfloor + \ldots +2^{\lfloor \log_2(n) \rfloor} \\ &=2^{\lfloor \log_{2} (n)\rfloor}+ n+ 2\left\lfloor\frac{n}{2}\right\rfloor + \ldots +2^{\lfloor \log_2(n) \rfloor} \\ &\leq (\lfloor \log_2(n) \rfloor +2)n \\ &\in \mathcal{O}(n\log(n)).\end{align} Is this process valid? Are there any other ways?
Proof using complete induction.
If $T(m) < c m \log(m)$ for $m < n$ then
$\begin{array}\\ T(n) &=2T(\lfloor\frac{n}{2}\rfloor)+n\\ &<2(c\lfloor\frac{n}{2}\rfloor \log(\lfloor\frac{n}{2}\rfloor))+n\\ &\le2(c\frac{n}{2} \log(\frac{n}{2}))+n\\ &= cn \log(\frac{n}{2})+n\\ &= cn \log(n)-cn \log(2)+n\\ &= cn \log(n)+(1-c \log(2))n\\ &= cn \log(n) \qquad\text{if } c > 1/\log(2)\\ \end{array} $