1
$\begingroup$

In Coreman , it's written :

The $O(n^2)$ bound on worst-case running time of insertion sort also applies to its running time on every input. The $\Theta(n^2)$ bound on the worst-case running time of insertion sort,however, does not imply $\Theta(n^2)$ bound on the running time of insertion sort on every input.

So, is there any difference between the two notations in terms of input? If so, then why does it use $\Theta(n^2)$ in worst case running time of insertion sort?

$\endgroup$
  • 1
    $\begingroup$ "is there any difference between the two notations in terms of input?" -- I don't understand this question. Landau notation is independent of algorithms. $\endgroup$ – Raphael Jun 29 '18 at 11:19
  • $\begingroup$ Do you mean Cormen? Or, more accurately, the famous book by Cormen, Leiserson et al. (often abbreviated CLRS)? $\endgroup$ – Raphael Jun 29 '18 at 11:22
  • 1
    $\begingroup$ @old It doesn't make sense to say that the algorithm takes $O(n^2)$ time on a particular input. $\endgroup$ – Solomonoff's Secret Jun 29 '18 at 13:58
3
$\begingroup$

It is important to understand the distinction between asymptotic bounds on time complexity, and the consideration of best, average, and worst-case performance. Many who are new to the subject tend to associate an $O$-bound as always indicating worst-case performance, but the best-case performance of an algorithm will always have an $O$-bound, just as the worst-case performance will always have an $\Omega$-bound.

I would like to add to Raphael's answer with an analogy.

Imagine that you live in a mountain town, where it snows fairly often. Your only means of transportation is a 20-year-old car that has seen better days. On most days, the car performs quite well, and you have no issues getting to where you need to go. However, on days when it snows, you are sometimes unable to get it out of the driveway. Even when you can get it out of the driveway, it does not function as well as it does on days when it is not snowing.

In this situation, it is clear that the worst possible performance ($O$) in the worst possible scenario is going to be the worst possible performance ($O$) for the car in any scenario! If this weren't the case, then how could it be the worst possible scenario? However, determining the best possible performance ($\Omega$) in the worst possible scenario tells you nothing about how the car performs in the best or average case. It is the same with insertion sort. (It is important to note though that for some algorithms, the $O$ and $\Omega$-bounds are actually the same in all cases).

Once you understand that insertion sort is $O(n^2)$ in all cases because it is $O(n^2)$ in the worst case yet it is $\Omega(n)$ in all cases despite being $\Omega(n^2)$ in the worst case, you will understand what the authors mean in that excerpt.

$\endgroup$
3
$\begingroup$

The best case runtime of insertion sort is linear, i.e. $\Theta(n)$. Therefore, there is no $\Theta(n^2)$ bound on all inputs, since that would require $\Omega(n^2)$ on all inputs.

This is just one example proving that while $O$-bounds on the worst-case translate to all-case, but $\Omega$-bounds (and therewith $\Theta$-bounds) do not. (Which is, of course, the point in the text.) You can also investigate this mathematically by unfolding the definitions.

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