# An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$

If $$n<100$$ then $$O(n^2)$$ is more efficient, but if $$n\ge 100$$ then $$O(n\log n)$$ is more efficient.

I am sure that this statement is valid, but I don't know how to prove it or justify it. Can someone please help me?

Your statement is meaningless, since $$O(n^2)$$ and $$O(n\log n)$$ are just upper bounds on the time complexity. If you know that $$A \leq 100$$ and $$B \leq 10$$, you have absolutely no idea which is larger, $$A$$ or $$B$$.

Let us correct your statement to

If $$n<100$$ then $$\Theta(n^2)$$ is more efficient, but if $$n \geq 100$$ then $$\Theta(n\log n)$$ is more efficient.

This statement still has no truth value, since we don't know which functions are represented by $$\Theta(n^2)$$ and by $$\Theta(n\log n)$$. What we do know is that for large enough $$n$$, the $$\Theta(n\log n)$$ algorithm would be more efficient.

Suppose you instantiate your statement with specific functions $$f(n) = \Theta(n^2)$$ and $$g(n) = \Theta(n\log n)$$. There is no reason to expect that there is a single crossover point. For example, take the following functions: $$f(n) = \begin{cases} 100 & \text{if } n < 20, \\ n^2 & \text{if } n \ge 20 \end{cases} \\ g(n) = \begin{cases} 50 & \text{if } n < 10, \\ 200 & \text{if } 10 \le n < 20, \\ 10^{300} n\log n & \text{if } n \ge 20 \end{cases}$$ As you can see, $$g(n)$$ is faster for $$n < 10$$, and then for (astronomically) large enough $$n$$.

While such definitions are artificial, in practice we could have (say) $$f(n) = 3n^2 + n\log n + 9n + 17$$ and $$g(n) = 10n\log n + 4\sqrt{n} + 50$$, which might have several crossover points (I haven't checked).

Finally, even if there is a single crossover point, there is no reason to expect it to be exactly $$n = 100$$. The exact crossover point(s) depend on the functions $$f(n),g(n)$$. The only way to determine it is by running the two algorithms and comparing the running times.

• So, every time it depends on which function we use for Θ(nlogn) and Θ(n^2) ? Apr 19, 2021 at 13:07
• Right, the answer depends on the exact functions used. Apr 19, 2021 at 13:08

We have $$O(n\log n) \subset O(n^2)$$ i.e. any $$f$$ from $$O(n\log n)$$ is also in $$O(n^2)$$.

Let's take any pair from $$O(n\log n)$$, for example $$f_1(n)=n$$ and $$f_2(n)=n\log n$$. Firstly we can consider them as $$f_1 \in O(n^2), f_2 \in O(n\log n)$$ and then we can consider them as $$f_2 \in O(n^2), f_1 \in O(n\log n)$$. It turns out, we cannot say that a representative of one class is definitely better than another.

Even more - we can formulate the following true sentence :

for any $$f$$ from $$O(n\log n)$$ we can find "faster" $$g$$ from $$O(n^2)$$.

$$O(n\log n)$$ is always faster. On some occasions, a faster algorithm may require some amount of setup which adds some constant time, making it slower for a small $$n$$.

So in reality, $$O(n^2 + i)$$ may be faster than $$O(n\log n + j)$$ if $$j$$ is sufficiently larger than $$i$$ for small enough $$n$$. There is certainly no number $$n$$ for which you can say there is definitely a crossover.

Note that we always ignore $$i$$ and $$j$$ in practice because big O notation is for when $$n$$ is large, so constants become increasingly meaningless and we only care about the fastest growing term.