5
$\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$
2

6 Answers 6

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
  • 4
    $\begingroup$ The example you gave is really good. +1. $\endgroup$
    – avi
    Mar 25, 2013 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, 2013 at 11:07
  • 1
    $\begingroup$ Indeed, see this post for an example of what @vonbrand mentions. $\endgroup$
    – Shaull
    Mar 25, 2013 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$
0
$\begingroup$

Short answer: $O(n^2)$ states an upper bound on the worst case complexity. I'd be quite right to say it is $O(n^3)$, or even $O(2^n)$ (check your definitions!). Saying the worst case complexity is $\Theta(n^2)$ says it is an upper and lower bound (within a constant factor, it is $n^2$ for large enough $n$). That is much stronger.

$\endgroup$
-1
$\begingroup$

In simple words, the running time of a programs is described as a function of its input size i.e. f(n).

The = is asymmetric, thus an+b=O(n) means f(n) belongs to set O(g(n)). So we can also say an+b=O(n^2) and its true because f(n) for some value of a,b and n belongs to set O(n^2).

Thus Big-Oh(O) only gives an upper bound or you can say the notation gives a blanket statement, which means all the inputs of a given input size are covered not just the worst case once. For example in case of insertion sort an array of size n in reverse order.

So n=O(n^2) is true but will be an abuse when defining worst case running time for an algorithm. As worst case running time gives an upper bound on the running time for any input. And as we all know that in case of insertion sort the running time will depend upon how the much sorted the input is in the given array of a fixed size. So if the array is sort the running will be linear.

So we need a tight asymptotic bound notation to describe our worst case, which is provided by Θ notation thus the worst case of insertion sort will be Θ(n^2) and best case will be Θ(n).

$\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
  • 5
    $\begingroup$ Theta notation has nothing to do with average case. $\endgroup$
    – SamM
    Apr 30, 2013 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, 2013 at 14:31
  • 3
    $\begingroup$ It's just plain wrong. See here. $\endgroup$
    – Raphael
    Apr 30, 2013 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.