2 Pointed out abuse of notation. edited Apr 16 '17 at 14:43 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges 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 answered Apr 16 '17 at 10:37 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges 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).