snippetModerate
Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?
Viewed 0 times
thetainsertionwhycasetimeitsrunningnotationdescribesuitable
Problem
The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.
$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of insertion sort, it implies that $O(n^2)$ is upper bound of algorithm no matter what type of input is, means it doesn’t matter whether input is sorted, unsorted, reverse sorted, have same values, etc the upper bound will be same $O(n^2)$. But this is not the case of insertion sort. Insertion sort running time depends on type of input used. So when the input is already sorted, it runs in linear time and doesn’t take more that $O(n)$ time.
Therefore to write insertion sort running time as $O(n^2)$ is technically not good.
We use $\Theta$-notation to write worst case running time of insertion sort. But I’m not able to relate properties of $\Theta$-notation with insertion sort, why $\Theta$-notation is suitable to insertion sort.If $f(n)$ belong to $\Theta(g(n))$ we write it as $f(n)= \Theta(g(n))$, then $f(n)$ must satisfies the properties. And properties state that there exits constants $c_1$, $c_2$ and $n_0$ such that $0$$\leq$$c_1\cdot g(n)$$\leq$$f(n)$$\leq$$c_2\cdot g(n)$ For all $n>n_0$. How does the insertion sort function lies between the $c_1\cdot n^2$ and $c_2\cdot n^2$ for all $n>n_0$.
Running time of insertion sort as $\Theta(n^2)$ implies that it has upper bound $O(n^2)$ and lower bound $\Omega(n^2)$. I’m confused as to whether the lower bound on insertion-sort is $\Omega(n^2)$ or $\Omega(n)$.
$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of insertion sort, it implies that $O(n^2)$ is upper bound of algorithm no matter what type of input is, means it doesn’t matter whether input is sorted, unsorted, reverse sorted, have same values, etc the upper bound will be same $O(n^2)$. But this is not the case of insertion sort. Insertion sort running time depends on type of input used. So when the input is already sorted, it runs in linear time and doesn’t take more that $O(n)$ time.
Therefore to write insertion sort running time as $O(n^2)$ is technically not good.
We use $\Theta$-notation to write worst case running time of insertion sort. But I’m not able to relate properties of $\Theta$-notation with insertion sort, why $\Theta$-notation is suitable to insertion sort.If $f(n)$ belong to $\Theta(g(n))$ we write it as $f(n)= \Theta(g(n))$, then $f(n)$ must satisfies the properties. And properties state that there exits constants $c_1$, $c_2$ and $n_0$ such that $0$$\leq$$c_1\cdot g(n)$$\leq$$f(n)$$\leq$$c_2\cdot g(n)$ For all $n>n_0$. How does the insertion sort function lies between the $c_1\cdot n^2$ and $c_2\cdot n^2$ for all $n>n_0$.
Running time of insertion sort as $\Theta(n^2)$ implies that it has upper bound $O(n^2)$ and lower bound $\Omega(n^2)$. I’m confused as to whether the lower bound on insertion-sort is $\Omega(n^2)$ or $\Omega(n)$.
Solution
You are confusing two different notions.
The definition of $\Theta$ that you give is correct, and indeed the running time of insertion sort, in the worst case, is $\Theta(n^2)$, since it has a quadratic running time.
The fact that this is the worst running time is somewhat irrelevant here. You have some function, and you are classifying it as $\Theta(n^2)$, because you can.
Indeed, the runtime of the algorithm in the best case can be a different function, which may or may not be $\Theta(n^2)$.
It may make more intuitive sense to just say that in the worst case, the runtime is $O(n^2)$, which implies that in all the cases the runtime is $O(n^2)$, but observe that this is also implied by the stronger $\Theta$ notations.
As an illustrative example, consider this: You can get home in two paths, one takes 10 km, and the other 3 km, but the 3 km is only open on certain hours of the day.
You can say the following: when you walk home, in the worst case you will walk exactly 10 km. This is true, and it implies that you always walk at most 10 km. But the former is a stronger claim, so why not use it?
The definition of $\Theta$ that you give is correct, and indeed the running time of insertion sort, in the worst case, is $\Theta(n^2)$, since it has a quadratic running time.
The fact that this is the worst running time is somewhat irrelevant here. You have some function, and you are classifying it as $\Theta(n^2)$, because you can.
Indeed, the runtime of the algorithm in the best case can be a different function, which may or may not be $\Theta(n^2)$.
It may make more intuitive sense to just say that in the worst case, the runtime is $O(n^2)$, which implies that in all the cases the runtime is $O(n^2)$, but observe that this is also implied by the stronger $\Theta$ notations.
As an illustrative example, consider this: You can get home in two paths, one takes 10 km, and the other 3 km, but the 3 km is only open on certain hours of the day.
You can say the following: when you walk home, in the worst case you will walk exactly 10 km. This is true, and it implies that you always walk at most 10 km. But the former is a stronger claim, so why not use it?
Context
StackExchange Computer Science Q#10763, answer score: 11
Revisions (0)
No revisions yet.