Running Time Question

Question

In what situations would a function of $\theta(n^2)$ perform better than $\theta(n \log n)$? I noticed that in comparing the two, they intersect at $n = 4$. After this, $n \log n$ takes over as being the better function. Would it just be, then, in the situation where n is less than 4 that the first function works better, or is there another way of looking at this problem?

Answer 1

Big-theta notation is concerned only with asymptotic behaviour. We say that a function - lets call it $g$ - is $\Theta(f(n))$ if there exists an $N$ such that for all $n$ larger than $N$, the following holds $$ k_1 f(n) \leq g(n) \leq k_2f(n) $$ for some constants $k_1$ and $k_2$. In particular, this means that all of the following are $\Theta(n^2)$: $n^2$, $n^2 + n$, $100n^2$, $10^{10^{10}}n^2$, and even $G\cdot n^2$, where $G$ is Graham's number.

Which function performs better - one which is $\Theta(n^2)$ or one which is $\Theta(n\log n)$ depends on the constant factors involved. If we suppose that these are the same, then your calculation of 4 is correct (assuming a base 2 log). If instead the constant factor in front of the $\Theta(n\log n)$ function is much larger than the one for the $\Theta(n^2)$ function, then the latter could perform better for all realistic inputs.