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

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$?

migrated from cstheory.stackexchange.comFeb 13 '13 at 2:05

This question came from our site for theoretical computer scientists and researchers in related fields.

• It wasn't clear from the original wording (before I edited it) whether "running time" actually means "worst-case running time". – JeffE Feb 13 '13 at 4:53
• For all $f$, $f \in \Theta(f)$. I think there is some (sub)text waiting to be made explicit here. – Raphael Feb 14 '13 at 6:51
• I suspect the original poster intended $f_A$ to be a simple function. – JeffE Feb 14 '13 at 12:58

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

• I think you could add just a short answer at the beginning to become a really great answer. – Alex Grilo Feb 13 '13 at 3:33
• @AlexGrilo thanks for the suggestion, fixed now – Sasho Nikolov Feb 13 '13 at 4:05
• Doesn't "running time" mean "worst-case running time" by default? – JeffE Feb 13 '13 at 4:54
• I only wrote this because there was some confusion with the other two answers – Sasho Nikolov Feb 13 '13 at 5:01
• @JeffE: Depends on who's talking, I guess. Most definitions I know define runtime $T(x)$ and then worst-case runtime $T(n) = \max \{ T(x) \mid |x|=n\}$. Afterwards, the distinction is typically dropped because most people in (the complexity-theory-part of) mostly talk about worst-case. – Raphael Feb 14 '13 at 6:48

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.

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.

• Alex, I don't think that answers the question. Can't big-theta just be of n^2 then? There is a big theta represention for every algorithm. – Bobby Brown Feb 13 '13 at 3:08
• A Theta representation for every algorithm means that the running time for every input must be within that function class. As I showed in my example, there is an algorithm for which this is not true. – Alex Grilo Feb 13 '13 at 3:39
• This is ambigious as to whether you are talking about worst case, average case, best case... etc. Big-O and Big-Theta are just was of classifying functions. Their definitions themselves don't actually say anything about which function you're analyzing, whether it be best or worst or average case running time. – jmite Feb 13 '13 at 6:33

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.

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

• I'm sure OP assumes the number of variables is equal to the arity of the function. But otherwise you are correct. – Pål GD Feb 13 '13 at 18:47

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