Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

migrated from cstheory.stackexchange.com Feb 13 '13 at 2:05

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

6 Answers

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

share|improve this answer
    
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
1  
Doesn't "running time" mean "worst-case running time" by default? –  JeffE Feb 13 '13 at 4:54
1  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
1  
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
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.