1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So, every time it depends on which function we use for Θ(nlogn) and Θ(n^2) ? $\endgroup$
    – gianluigi
    Apr 19 '21 at 13:07
  • 1
    $\begingroup$ Right, the answer depends on the exact functions used. $\endgroup$ Apr 19 '21 at 13:08
1
$\begingroup$

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)$.

$\endgroup$
-4
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.