Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top