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?