4
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ The example you gave is really good. +1. $\endgroup$ – avi Mar 25 '13 at 9:23
  • 1
    $\begingroup$ It isn't the case for the worst case of insertion sort, but you might come across a function $T(n)$ that is $n$ if $n$ is even and $n^2$ if $n$ is odd. Then you can say $T(n) = O(n^2)$, but not $T(n) = \Theta(n^2)$, $\endgroup$ – vonbrand Mar 25 '13 at 11:07
  • 1
    $\begingroup$ Indeed, see this post for an example of what @vonbrand mentions. $\endgroup$ – Shaull Mar 25 '13 at 11:14
3
$\begingroup$

So, before going ahead, just let me clarify one thing. Theta - Θ(g(n)) indicates asymptotic tight bounds. Your function(insertion sort running time) is sandwiched between constant factors of g(n).

Big O - O(g(n)) indicates asymptotic upper bounds. So, no matter what your function is, if it is a O(g(n)) it is bound to be less by a constant factor of g(n).

Coming to the insertion sort running time, O(n²) and Θ(n²) are both the worst case scenario i.e. when the array is in a decreasing order.

But in the best case scenario i.e. when the array is sorted, it is not Θ(n²) but Θ(n). But if you want to represent the same it can be both O(n²) and O(n).

So, O(n²) holds true for both the worst and the best case where as Θ(n²) holds only for the worst case. That's the reason, Big O can be used to make blanket statements i.e. for any kind of input, it holds. Hope it helped.

$\endgroup$
1
$\begingroup$

You are correct that $\Theta$ cannot be used to describe the runtime of insertion sort on arbitrary input, because its performance varies too dramatically.

However, we're talking worst case, not general case; e.g. for every $n$, we let $A_n$ be the input that takes the longest for insertion sort to sort. Then the assertion that the running time of "call insertion sort with input $A_n$" is given by $\Theta(n^2)$.

$\endgroup$
-5
$\begingroup$

In general you don't use the theta function for the worst case, but for an average one.

The insertion sort algorithm has a linear time when the array is already sorted: Ω(n); and a quadratic time when it's sorted in the opposite order: O(n^2).

An average case won't have many already sorted elements so it will be next to the worst case[*]; a better one, but within the same quadratic order: Θ(n^2).

As a conclusion, you should always use both Ω and O function for describing the algorithm but, if the majority of the cases is around a Θ function, is ok to use only it.


[*]: That's because is the inner cycle that bears on the resulting time.

$\endgroup$
  • 3
    $\begingroup$ Theta notation has nothing to do with average case. $\endgroup$ – SamM Apr 30 '13 at 0:50
  • $\begingroup$ I was trying to simplify… ^^" By the way I'm studing those things in these days (first year of university) so every correction is appreciated. :) $\endgroup$ – dezzeus Apr 30 '13 at 14:31
  • 1
    $\begingroup$ It's just plain wrong. See here. $\endgroup$ – Raphael Apr 30 '13 at 21:53

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.