Solving Recurrence Relation (quicksort )
Your mistake is $2\mathcal{O}(n/2) = \mathcal{O}(n/2)$. More generally, in order not to be confused, it is much better to replace $\mathcal{O}(n)$ with $An$ for some constant $A$, which can be taken as $1$ without loss of generality. Then we have
$$
\begin{align*}
T(n) &amp;\leq 2T\left(\frac{n}{2}\right) + n \\
&amp;\leq 4T\left(\frac{n}{4}\right) + 2 \frac{n}{2} + n \\
&amp;\leq 8T\left(\frac{n}{8}\right) + 4 \frac{n}{4} + 2 \frac{n}{2} + n \\
&amp;\leq \dots
\end{align*}
$$
More generally, we get
$$
T(n) \leq 2^k T\left(\frac{n}{2^k}\right) + kn.
$$
Assuming $n = 2^k$ and $T(1) = C$, this gives
$$
T(n) \leq 2^kC + k2^k = \mathcal{O}(n\log n).
$$
You can get a lower bound in exactly the same way.