# What is the difference between Big O and Theta notation in terms of inputs?

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?

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

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.

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