Solving Recurrence Relation (quicksort ) I know quicksort to have a runtime of $\mathcal{O}(n \log_2 n)$

However trying to solve for it I get something different and I am not sure why that is.

Ok, so solving recurrence relations can be done several different ways.

The recurrence relation for quicksort is:

$$T(n) = 2 T(\frac{n}{2}) + \mathcal{O}(n)$$

Reinserting a few times we get:

$$T(n) = 2 \left[ 2 T(\frac{n}{4}) + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$T(n) = 2 \left[ 2  \left[ 2 T(\frac{n}{8}) + \mathcal{O}(\frac{n}{4}) \right] + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$...$$

Which can be generalised to:

$$T(n) = 2^kT(\frac{n}{2^k})+\sum_{i=0}^{k-1} \mathcal{O}(\frac{n}{2^i})$$

Now the sum can be solved like this:

$$\sum_{i=0}^{k-1} \mathcal{O}\left(\frac{n}{2^i}\right) = \sum_{i=0}^{k-1} \mathcal{O}\left(n\left(\frac{1}{2}\right)^i\right) = \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}$$

$$\lim_{k \to \infty} \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}  = \frac{n}{1 - \frac{1}{2}} = 2n$$

So the recurrence can be simplified accordingly:

$$T(n) = 2^kT(\frac{n}{2^k})+2n$$

Assuming $T(1) = C$ we get $$T(n) = 2^{\log_2 n}T(\frac{n}{2^{\log_2 n}})+2n = n C + 2n$$

And $ n C + 2n \not \in \mathcal{O}(n \log_2 n)$

Can somebody explain my error to me?
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.