What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$? Problem:
Suppose the running time of a certain algorithm is $O(n \ln n)$. We happens to the running
time of the algorithm if $n$ doubles.
Answer:
Let $R_1$ be the running time of the algorithm when the input is of size $n$. Let $R_2$ be the running time of the algorithm when the input is of size $2n$. Let $R = R_2 / R_1$.
\begin{align*}
R &amp;= \frac{ 2n \ln (2n)}{ n \ln n } =  \frac{ 2 \ln (2n)}{ \ln n } \\ 
R &amp;= \frac{ 2 ( \ln(2) + \ln(n))}{ \ln n } =
    \frac{ 2 ( \ln(2) )}{ \ln n } + \frac{ 2 ( \ln(n))}{ \ln n }\\ 
R &amp;= \frac{2 \ln(2)}{ \ln n } + 2 \\
\end{align*}
This does not seem right to me. Is it? If it is wrong, where did I go wrong?
I  suggest following property: if for functions $g,f \gt 0$ we have $f \sim kg$, for some constant $k\gt 0$  i.e. $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=k$ and both, $g$ and $f$, have not zero as limit point, then $O(f)=O(g)$.
Proof:
Let's consider $\phi \in  O(f)$, then we have $\phi \leqslant C f \leqslant C (k+\varepsilon)g$ for appropriate $C, \varepsilon$ and $n \gt N.$ So $O(f) \subset O(g)$. Using, that we have also $\lim\limits_{n \to \infty}\frac{g(n)}{f(n)}=\frac{1}{k} \gt 0$, we obtain reverse including.
Based on brought property we can say, that running time $O(n \ln n)$ does not change if we double $n$:
$$O(n \ln n) = O(2n \ln 2n)$$