2 Pointed out abuse of notation.
source | link

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)$. InHowever, 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 stillabuse notation a little harder and say that 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'$.

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)$. In this case, where the best and worst case running times are different, we can still say that 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).

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

1
source | link

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)$. In this case, where the best and worst case running times are different, we can still say that 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).