2
$\begingroup$

This is a question posted for extra practice (i.e., not for credit):

Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.

I'm not sure how to approach it. I see lots of near-answers online using $O(\cdot)$, but $\Theta(\cdot)$ is a little different because it means there is both an upper and a lower bound of $n^2$ and $n \log(n)$, respectively.

So, at its absolute best case, a $n^2$ algorithm may run in $\frac{1}{a}n^2$ time, which for large $a$ may be very fast compared to most quadratic algorithms. However, since $a$ is constant, as $n \to \infty$, the time for even a $\frac{1}{a}n^2$ algorithm will far surpass a $bn\log(n)$ algorithm, even if $b$ is very large.

This would lead me to believe the answer is no, an algorithm that runs in $\Theta(n^2)$ cannot run faster than a $\Theta(n \log n)$ algorithm when analyzed asymptotically as I have done.

With this said, if the thing that makes the $\Theta(n \log n)$ algorithm $\Theta(n\log n)$ happens very frequently but the thing that makes the $\Theta(n^2)$ algorithm $\Theta(n^2)$ does not happen frequently at all (either due to the nature of the algorithm or optimized design), then the amortized complexity of the $\Theta(n^2)$ algorithm may in fact be less than that of the $\Theta(n \log n)$ algorithm — even if the asymptotic complexity says otherwise — right?

If the two complexities given were $O(\cdot)$ rather than $\Theta(\cdot)$ then I may be inclined to side with the latter argument. The presence of the lower bound that $\Theta(\cdot)$ implies is giving me second thoughts though. Can anyone help point me in the right direction here and clarify if it seems that I am misunderstanding the use of $\Theta(\cdot)$ for asymptotic versus amortized analysis.


Edit: I don't think this is a duplicate of Sorting functions by asymptotic growth. I am familiar with how to use limits, etc. to classify and sort algorithms asymptotically. Speaking strictly in terms of asymptotics, I think the answer to my question is definitely no. The question quoted (as worded) seems more general though; it wants to know if there is any way that a $\Theta(n^2)$ algorithm can out perform a $\Theta(n \log n)$ algorithm. Is such an occurrence possible when considering amortized analysis rather than asymptotic analysis and the algorithms are structured as described above? Or is this irrelevant and the answer is still no?

$\endgroup$
4
  • $\begingroup$ Possible duplicate of Sorting functions by asymptotic growth $\endgroup$
    – Evil
    Jun 28, 2019 at 2:42
  • 4
    $\begingroup$ What does “faster” mean? $\endgroup$ Jun 28, 2019 at 3:51
  • 3
    $\begingroup$ Asymptotic notation doesn’t say “faster”. It rather says “scales better, given that $n$ keeps growing indefinitely”. $\endgroup$ Jun 28, 2019 at 7:15
  • 1
    $\begingroup$ Yes, if the constants hidden in the asymptotic notation are larger for the n log n algorithm and n is small. $\endgroup$
    – mo2019
    Jun 29, 2019 at 12:12

3 Answers 3

4
$\begingroup$

Asymptotically, you're right: for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster. However, this is only true for big enough $n$. It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about".

For a specific example of this, look at matrix multiplication algorithms. For $n\times n$ matrices, the standard pencil-and-paper algorithm takes time $\Theta(n^3)$. Strassen's algorithm essentially considers the matrix to be a matrix of smaller matrices and improves the running time to $O(n^{2.81})$ but the algorithm is more complicated, so the constants hidden by the big-$O$ mean that Strassen is only likely to be faster for about $n>100$. Coppersmith–Winograd is $O(n^{2.37})$ but is even more complicated and, as far as I'm aware, isn't used in practice, because it only wins on matrices that are too big for people to want to multiply anyway.

Another aspect is that some algorithms might be better or worse than others on real computers. If an algorithm's data access patterns play nicely with the cache, it can be thousands of times faster than code that sprays memory accesses all over the address space: algorithms based on hash tables are particularly bad at for that. $n^2 < 1000n\log_2 n$ for all $n$ less than about $14\,000$. Likewise, an algorithm with a simpler branching structure in the code might run faster because the CPU pipeline is full more of the time.

$\endgroup$
1
  • $\begingroup$ You say "for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster". Tthe truth is that "for big-enough $n$, the $\Theta(n\log n)$ algorithm is faster". $\endgroup$
    – Thumbnail
    May 4, 2020 at 0:14
2
$\begingroup$

The definition of $\Theta$ includes two constants that the function is multiplied with, and a smallest n where the relation applies. (There is an $n_0$ such that for all n ≥ $n_0$, $c_1 g(n) ≤ f(n) ≤ c_2 g(n)$).

If $n < n_0$ then anything can happen. And if one algorithm comes with much smaller constants, then it may stay faster for some quite large n. Asymptotically, no.

Let's say you have an algorithm examining n items. Most of the work is done in linear time. But one in a million of those items is "hard" and you take $\mathcal O(m^2)$ where m is the number of "hard" items. Another algorithm takes $\mathcal O (n \log n)$ no matter what. If $n = 1,000,000,000$ and $m = 1000$, the first algorithm will be a lot faster.

$\endgroup$
0
$\begingroup$

This would hold that for small cases, e.g., let n = 2, we know that $ 100nlogn = \Theta (n \log n)$ will be larger than $ 2n^2 = \Theta (n^2)$.

We can also use our 2 classic sorting algorithm as an example.

Insertion sort is $\Theta (n^2)$ runtime.

Merge sort is $\Theta (n \log n)$ runtime.

For a sorted array, insertion sort runs close to $\Theta (n)$ while merge sort is $\Theta (n \log n)$.

$\endgroup$
7
  • $\begingroup$ The question talks about $\Theta$ while this answer talks about $\Omega$. Those sounds very different to me. $\endgroup$
    – John L.
    May 2, 2020 at 20:00
  • $\begingroup$ I am afraid that insertion sort is not $\Theta(n^2)$. Insertion sort is $\Theta(n^2)$ at worst time. Insertion sort is $O(n^2)$ in general. In fact, (you pointed out) the insertion sort runs in $\Theta(n)$ time on a sorted array. Note that merge sort is $\Theta(n\log n)$ in worst time and in best time. $\endgroup$
    – John L.
    May 3, 2020 at 1:39
  • $\begingroup$ yea, it's asymptotically tight. So it's theta and Big-O are the same. no? $\endgroup$
    – Peter
    May 3, 2020 at 1:45
  • $\begingroup$ No, the time-complexity of insertion sort is not $\Theta(n^2)$, since it can run in $O(n)$ time sometimes. $\endgroup$
    – John L.
    May 3, 2020 at 4:16
  • $\begingroup$ @JohnL If you're measuring mean time, insertion sort is $\Theta(n^2)$. $\endgroup$
    – Thumbnail
    May 5, 2020 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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