How can a quadratic algorithm be faster than a linearithmic one?

I have to solve the following problem:


Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if $nk$.
Also, I know that $O(n^2)$ comes from a polynomial of degree 2 that might have a coefficient and other terms of lower degree.

I do not find how to relate this facts in order to make a conclusion although I suspect that constants $C$ and $k$ could play an important role in such a conclusion.

I will very much appreciate any clue so I can get a better idea about how to formulate an answer.

All you know is that an $O(n\log n)$ algorithm is eventually (a lot) faster than an $O(n^2)$ algorithm, but for any specific value of $n$, you can't say anything. Indeed, the asymptotic growth of the function doesn't depend on its value on $n < 100$. This means that if $f(n) = O(n^2)$ then for all $c_1,\ldots,c_{99}$, the following function is also $O(n^2)$:
$$
f'(n) = \begin{cases} c_n & \text{if } n < 100, \\ f(n) & \text{if } n \geq 100. \end{cases}
$$
So asymptotic notation is completely uninformative regarding the performance of algorithms on specific values of $n$.

You could say that functions such as $f'(n)$ are artificial and never really occur in practice. This is not quite true (you can hard-code some auxiliary information for small $n$, for example), but even if you consider "natural" functions, asymptotic notation doesn't help you to determine anything other than asymptotics: consider for example $n^2$ against $10^{100} n\log n$ (such examples definitely happen in practice, for example in fast matrix multiplication).

StackExchange Computer Science Q#44289, answer score: 7