Tight Bound of the Insertion Sort
So is $\Theta$ undefined for insertion sort?


This question contains a category error. It's like saying, "I know that Donald Trump has a height of at least&nbsp;5 and at most&nbsp;7. So are numbers undefined for Donald Trump?

$\Theta$&nbsp;is notation for expressing the growth rate of mathematical functions. "Insertion sort" is not a mathematical function, so if you want to talk about $\Theta$ and insertion sort in the same sentence, you need to say what property of insertion sort you're measuring with a mathematical function that you wish to describe with&nbsp;$\Theta$.

We measure the resource usage of algorithms in terms of the length of the input, which is usually denoted&nbsp;$n$.  You've proposed a function which is the number of execution steps of insertion sort on some input. However, this is a function of the input itself, not of its length. Some inputs of length&nbsp;$n$ will take roughly $n$&nbsp;steps to sort (I'm using "roughly" to hide constant factors), and some inputs of length&nbsp;$n$ will take roughly $n^2$&nbsp;steps. So you can't write this as a function of&nbsp;$n$ at all&nbsp;&ndash; the number of steps required isn't just a function of the length of the input but, rather, it's a function of the whole input.  Because the thing you're trying to measure isn't a function of the length of the input, you can't directly measure it using&nbsp;$\Theta$ at all.

So we need to come up with a function that does just depend on the length of the input. Two natural functions are the best-case and worst-case number of execution steps. We know that, for an input of length&nbsp;$n$, the best case is that insertion sort finds that the input is already sorted, and in this case, it takes a linear number of steps.  No more, no less, so we're entitled to say that the best-case running time of the algorithm is $\Theta(n)$. Similarly, we're entitled to say that the worst-case running time is $\Theta(n^2)$.

If the best and worst case was (asymptotically) the same (up to constant factors), then the running time would actually just be a function of the length of the input, so it would make sense to say that the running time was, e.g., $\Theta(n\log n)$. However, unless the running time really is a function of&nbsp;$n$, this is an abuse of notation. In the case or insertion sort, where the best and worst case running times are different, we can abuse notation a little harder and say the running time is $\Omega(n)$ and $O(n^2)$. This says that, for any (sufficiently large) input, the running time will be somewhere between $n$ and&nbsp;$n^2$ steps (up to constant factors) but, again, there is no actual function of&nbsp;$n$ that is "the running time." It would be more formal to say that the running time&nbsp;$T(x)$ for an input&nbsp;$x$ satisfies $c|x|\leq T(x)\leq c'|x|^2$ for large enough&nbsp;$|x|$ and some constants $c$ and&nbsp;$c'$.