# Tight Bound of the Insertion Sort

I'm asking this question because I was confused by some of the articles in the internet.

I already know that the asymptotic lower and upper bounds of insertion sort is $\Omega(n)$ and $O(n^2)$.

Therefore according to my understanding of the $\Theta$ notation, we cannot make a statement about the $\Theta$ for all cases.

So is it $\Theta$ undefined for the insertion sort?

Or is it $\Theta(n^2)$?

• Article on how $Ө$ is defined :-stackoverflow.com/questions/10376740/… – Garrick Apr 16 '17 at 10:08
• "I already know" -- where from? Which exact functions are these bounds for? – Raphael Apr 16 '17 at 11:03
• I think you may profit from our reference questions. – Raphael Apr 16 '17 at 11:06
• @Raphael number of comparisons. – Synex Apr 16 '17 at 11:09
• @Synex For which class of inputs? – Raphael Apr 16 '17 at 18:26

So is $\Theta$ undefined for insertion sort?
$\Theta$ 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 $\Theta$.
We measure the resource usage of algorithms in terms of the length of the input, which is usually denoted $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 $n$ will take roughly $n$ steps to sort (I'm using "roughly" to hide constant factors), and some inputs of length $n$ will take roughly $n^2$ steps. So you can't write this as a function of $n$ at all – 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 $\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 $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 $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 $n^2$ steps (up to constant factors) but, again, there is no actual function of $n$ that is "the running time." It would be more formal to say that the running time $T(x)$ for an input $x$ satisfies $c|x|\leq T(x)\leq c'|x|^2$ for large enough $|x|$ and some constants $c$ and $c'$.