1
$\begingroup$

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)$?

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

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 5 and at most 7. So are numbers undefined for Donald Trump?

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

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