Extra space of MergeSort
$O(n)$ denotes the set of all functions $f(n)$ that are, for sufficiently large $n$, at most a constant factor larger than $n$. The notation $f(n) = O(n)$ is confusing because it really means $f(n) \in O(n)$.

E.g. $2n+5 \in O(n)$, $n/2 \in O(n)$, $\sqrt{n} \in O(n)$, $n + log\ n \in O(n)$ (the latter, because indeed $log\ n$ is negligible compared to $n$, e.g. $n + log\ n &lt; 2n$ and $2n \in O(n)$).

However, $n^2 \notin O(n)$ because there's no constant $k$ that can make $n^2 &lt; k n$ for all sufficiently large $n$.