Can every algorithm's running time be expressed as $\Theta(f(n))$?

Question

That is, can the running time of every algorithm $A$ be written as $O(f_A(n))$ and $\Omega(f_A(n))$, for the same function $f_A$?

Answer 1

The best case running time and the worst case running time on inputs of length $n$ can each be expressed in this way (as can any function of $n$), however, the two measures do not need to coincide. Details follow.

The running time of an algorithm is not a function only of input size $n$ but a function of the input and there are various running time measure that you can define as functions of $n$. You can define $f_A(n)$ as the worst case (=largest) running time over inputs of size $n$ and $g_A(n)$ as the best case (=smallest) running time over inputs of size $n$. Alex's argument is basically that $f_A(n) = \Theta(g_A(n))$ is not true for every algorithm $A$. The big-oh, big-omega and big-theta notations are used to denote the growth rate of a function as its argument goes to infinity - by itself $\Omega()$ doesn't say whether you are talking about worst case running time or best case running time, and neither does $O()$. So for the insertion sort you have:

• $f_A(n) = \Theta(n^2)$ because you never need more than $O(n^2)$ steps to finish sorting and for each $n$ there is an input (reverse order) for which the algorithm takes at least $C n^2$ time for some constant $C$.

• $g_A(n) = \Theta(n)$ because for each $n$ there is an input (sorted array) for which insertion sort runs in linear time and of course you need at least linear time to read the array.

And of course $f_A(n) = \Theta(f_A(n))$ and $g_A(n) = \Theta(g_A(n))$. However, $f_A$ and $g_A$ need not be monotonically increasing, they can oscillate infinitely often.

If you feel comfortable with all that you might check this discussion too: http://blog.computationalcomplexity.org/2005/01/big-omega.html

Answer 2

Yes. If your alphabet $\Sigma$ is finite then the number of words of length $n$ is finite for every $n \in \mathbb{N}$.

This means that if you have an algorithm A, you can define $f_A$ as being $f_A(n) = \max_{w}t(A(w))$ where the $\max$ is taken over all strings of length $n$ and $t(A(w))$ is the time measure of $A$ run on input $w$. The worst case complexity of $A$ is then $\Theta(f_A)$.

You can define it similarly for average and best case by taking respectively average and minimum of all time measures.

Answer 3

To show that Sasho's answer doesn't just hold for pathological algorithms, here's an example.

Consider a factorization algorithm that (1) tests whether a number $N$ is prime, (2) checks whether $N$ is divisible by small primes, (3) uses a factorization algorithm that is superpolynomial (such as all known ones).

In the cases where $N$ is prime or $N$ only has small prime factors, the algorithm runs in polynomial time in the input size $\log N$. For the hardest numbers to factor, the best known algorithm runs in time $2^{\Omega(\log^{1/3} N)}$, much slower.

Answer 4

No. For some inputs an algorithm can run faster or slower.

For instance, insertion sort can run in $O(n)$ time when the input array is already sorted but it requires $\Omega(n^2)$ time for arrays in reversed order.

Answer 5

As a simple proof-by-contradiction take a look at any algorithm who's complexity depends on more than one variable, e.g.: $\mathcal{O}(nk)$.

In such a case it is rarely possible to express running time as $\mathcal{O}\big( f(n) \big)$.

Answer 6

Consider the following problem:

1. Input: a list $l$ of integers of length $n$ and an integer $m$.
2. Output: a list $l'$ containing the elements of $l$ in ascending sorted order if $n$ is even, or a Boolean value indicating whether $m$ is contained in $l$ if $n$ is odd.

Consider the following algorithm:

if n % 2 = 0 return sort(l)
else if n % 2 = 1 return search(l, m)

The best-case behavior of this is that $n$ is odd, in which case the lower bound is $\Omega(n)$ (assuming linear search); the worst-case behavior is when $n$ is odd, in which case the upper bound is $O(n \log n)$. So the "universal" case of this algorithm does not have a $\Theta$ bound.

Note that the best and worst cases of this algorithm do have $\Theta$ bounds. Bounds apply to cases, not to algorithms (when we apply bounds to algorithms directly, a case is usually understood; often we mean the worst case, but sometimes - as in this example - we mean a sort of "universal" case considering all inputs without weighting).