Which grows faster, n log n or n squared?

Because $n \log n$ contains an extra logarithm, it is tempting to read it as the more decorated and therefore heavier expression. The decoration is not an extra factor of $n$. Write the two as $n$ times something: $n \log_2 n$ is $n$ times $\log_2 n$, while $n^2$ is $n$ times $n$. For every integer $n > 1$, $\log_2 n < n$, so $n \log_2 n < n^2$. The logarithm grows very slowly: at a million, $\log_2 n$ is still under $20$, which is nothing beside the million in the other factor. A constant factor can hide this at small sizes, but it cannot change which expression eventually dominates.

The doubling ratio is the quickest mental test. For $n^2$, replacing $n$ by $2n$ gives $(2n)^2 = 4n^2$, so the cost quadruples exactly. For $n \log_2 n$, the same replacement gives $2n(\log_2 n + 1)$, which is $2n\log_2 n$ plus $2n$. The ratio is $2(1+1/\log_2 n)$, so it is slightly more than $2$ and falls towards $2$ as $n$ grows. At $n=1024$ it is $2(1+1/10)=2.2$. At $n=64$ doubling to $128$: $64 \log_2 64 = 384$ becomes $128 \log_2 128 = 896$, a ratio of $2.33$, while $4096$ becomes $16{,}384$, a ratio of $4$. A procedure that quadruples when the input doubles is pulling away from one that a little more than doubles.

The asymptotic statement is one directional. $n \log n$ is $O(n^2)$ because the ratio $n \log_2 n / n^2 = \log_2 n / n$ tends to $0$. It is not true that $n^2$ is $O(n \log n)$, since the reverse ratio $n/\log_2 n$ tends to infinity. That is the formal version of the same arithmetic.

The statement is about growth, not about a stopwatch at every size. At small $n$, lower order terms and constant factors can make a quadratic procedure faster than an $n \log n$ procedure. Insertion sort, which is quadratic in the worst case, often beats merge sort below a few dozen items because its inner loop is tiny and merge sort allocates and copies. The crossover is a measured number, and below it the worse growth shape can be the right choice. The same caution applies to the logarithm's base: changing from base 2 to natural log multiplies $n \log n$ by a constant, which shifts timings but does not change the growth class. The formal order is still $n \log n$ below $n^2$; only the measured winner at that size changes.

At a million rows, the $n \log n$ procedure is still standing: its count is about $19.9$ million, while the $n^2$ procedure is at a million million. If a design choice is between the two, the crossover question is only relevant below the size where constants matter; above it, the $n \log n$ side wins by the ratio $n/\log_2 n$.