<p>The right definition of $f(n)=\Omega(n^2)$ is that there exists some $k&gt;0$ such that for infinitely many $n$, $f(n)\geq kn^2$. The infinitely-often definition for lower bounds handles your issues and is how we use it in practice.</p>

<p>I did a <a href="http://blog.computationalcomplexity.org/2005/01/big-omega.html">post</a> on this back in 2005.</p>

<p>Some textbooks get this definition right, some don't. </p>

CC BY-SA 2.5
2011-03-19T15:32:43.767Z
Knuth disagrees with you: http://portal.acm.org/citation.cfm?id=1008329
Jeffε
CC BY-SA 2.5
2011-03-19T16:22:08.570Z
CLRS and Wikipedia also disagree with you. The infinitey-often definition is a noteworthy alternative, but seems to be less widely used.
Anonymous
CC BY-SA 2.5
2011-03-22T22:16:55.683Z
i think these definitions all agree when the set of exceptions is measure 0.
Carter Tazio Schonwald
CC BY-SA 2.5
2011-03-25T15:26:31.947Z
The problem with "infinitely often" definitions is that they don't usually exclude "infinitely often not".  So we have the horrible consequence that with this definition $f(n)=\Omega(n^2)$ but _also_ $f(n)=o(n+1)$, where the $\Omega$ and $o$ are meant to be strict orders in some sense.  I really dislike this.  At least @Carter's suggestion of measure 0 exceptions is a bit less horrible, while still allowing a finer order than the usual one.
András Salamon
CC BY-SA 2.5
2011-03-26T18:34:48.303Z
@András: I don't follow. If you define $\Omega$ using this version (infinitely often) and $o$ as usual (for sufficiently large $n$), I don't see how you could have $f(n) = \Omega(n^2)$ and $f(n) = o(n+1)$.
Jukka Suomela
CC BY-SA 2.5
2011-03-26T23:38:49.660Z
@Jukka: If you define $\Omega$ this way then $o$ should probably be defined in a similar way?
András Salamon
CC BY-SA 2.5
2011-03-27T08:14:31.093Z
@András: I don't think so. Has anyone ever used (or suggested) a similar definition of $o$ or $O$?
Jukka Suomela
CC BY-SA 2.5
2011-03-27T16:34:18.453Z
@Jukka: No, I'm misusing $o$ here.  As you hint I have to correct my argument to use $O$ instead of $o$.  Let me therefore restate the actual objection without using $o$ or $O$.  With "infinitely often", one has the anomaly that $n = \Omega(f(n))$, $f(n) = \Omega(n^2)$, yet $n \ne \Omega(n^2)$.  So $\Omega$ doesn't even form a preorder.
András Salamon
CC BY-SA 2.5
2011-03-19T13:50:29.113Z
2011-03-19T13:50:29.113Z
Lance Fortnow
<p>With <a href="http://dx.doi.org/10.1145/1008328.1008329" rel="nofollow">Knuth</a>'s definition you can assert only $f(n)\in\Omega(n)$. As
you observe, this is not intuitive and happens for functions <a href="http://dx.doi.org/10.1145/382242.382835" rel="nofollow">Vitányi and Meertens</a> call "wild". They propose to define</p>

<p>$$\Omega(f(n))=\{ g \mid \exists \delta&gt;0:\forall n_0&gt;0:\exists n&gt;n_0: g(n)\geq \delta f(n)\}\textrm{.}$$</p>

<p>(This is the same as Lance's definition.) With this definition $f(n)\in\Omega(n^2)$.</p>

CC BY-SA 2.5
2011-03-25T14:51:57.240Z
2011-03-25T14:51:57.240Z
Marcus Ritt
<p>I think we should distinguish between two things:</p>

<ul>
<li>a lowerbound for a function</li>
<li>a lowerbound for a problem (algorithm)</li>
</ul>

<p>For functions, when we fix an order the definition of <a href="http://en.wikipedia.org/wiki/Lower_bound" rel="nofollow">lowerbound/upperbound</a> follows from it. If the order relation is asymptotic <a href="http://en.wikipedia.org/wiki/Majorization#In_recursion_theory" rel="nofollow">majorization</a> (ignoring constant factors)</p>

<p>$$f \preceq g : \exists c,n \forall m&gt;n. \ f(x) \leq c g(x) $$ </p>

<p>then the definition is the usual definition of $O$ and $\Omega$. Both of them are used extensively in other areas like combinatorics.</p>

<p>But when we talk about a lowerbound for a problem (an algorithm) what we really want to say is that the problem requires certain amount of resources (for running the algorithm solving the problem). Often the complexity classes are parametrized by functions like $\mathbf{Time}(t(n))$, and we simple say that the problem is lower bounded by a function, but this only works for nice functions (e.g. the running time of the algorithm is monotone, etc.). What we want to say in these cases is that we need $n^2$ running time to solve the problem, i.e. less than $n^2$ running time is not sufficient, which formally becomes Lance's definition that the running time of the algorithm is not in $o(t(n))$. </p>

CC BY-SA 2.5
2011-03-25T00:27:33.790Z
2011-03-25T00:36:58.183Z
2011-03-25T00:36:58.183Z
Kaveh
<p>I don't know about the most widely used, but I believe I know of the oldest usage (for computer science anyway).</p>

<p>In the 1965 paper by Hartmanis &amp; Stearns "On the computational complexity of algorithms", Corollary 2.1 is:</p>

<blockquote>
  <p>If $U$ and $T$ are time-functions such that $\inf_{n \rightarrow \infty} \frac{T(n)}{U(n)} \geq 0 $ then $S_{U} \subseteq S_{T}$</p>
</blockquote>

<p>where $S_{K}$ is the complexity class of all problems computable in $O( K(n) )$ . T(n) must obey $ T(n) \geq n/k$ for some integer $k$ and all $n$ and $T(n) \leq T(n+1)$ , but it doesn't have to be time-constructible.</p>

<p>Your function obeys the first rule for $k = 1$ but fails to obey the second rule.</p>

<p>Corollary 2.2 is the reciproral of the above and uses limit supremum, but still has these requirements. I guess as algorithms got more complex by the years, it is possible that the requirements have been relaxed.</p>

CC BY-SA 2.5
2011-03-19T23:59:24.280Z
2011-03-20T00:19:34.100Z
2011-03-20T00:19:34.100Z
chazisop
<p>Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.</p>

<ol>
<li><p>So, what is the lower bound of the problem? The way I understood it is just the lower bound of $f(n)$. But we know that $f(n) = \Omega(n^2)$ implies that there exists constant $k$, $n_0$ such that for all $n &gt; n_0$, $f(n) &gt; kn^2$, which is not true. Thus it seems that we can only say $f(n) = \Omega(n)$. 
But usually, we will call the problem has a lower bound of $\Omega(n^2)$, right?</p></li>
<li><p>Assuming that $g(n) = \Omega(n^2)$, which means that there exists constant $k$, $n_0$ such that for all $n &gt; n_0$, $g(n) &gt; kn^2$. Let's also assume a problem has running time $g(n)$. If we can reduce this problem for all the primes $n$ to another problem (with same input size), can we say the running time of the other problem has a lower bound of $\Omega(n^2)$? </p></li>
</ol>

CC BY-SA 2.5
2011-03-19T14:02:41.037Z
This is why mathematicians use lim sup and lim inf.
Peter Shor 
CC BY-SA 2.5
2011-03-19T18:17:51.933Z
So I think I understand the difference. I think post people will just understand Omega as infinitely often.

But in case I want to make an explicit distinction, are there any notations I can use other than expanding it?
Wei Yu
CC BY-SA 2.5
2011-03-19T18:30:03.397Z
@Wei Yu: lim sup and lim inf. You say $$\limsup \frac{g(n)}{n^2} \geq k$$ for some constant $k$ if you want to  say that $g(n) \geq k n^2$ infinitely often, and  $$\liminf \frac{g(n)}{n^2} \geq k$$ if you want to say $g(n) \geq k n^2$ for all sufficiently large $n$. $$\ $$ Especially if you're talking to mathematicians.
Peter Shor 
CC BY-SA 2.5
2011-03-20T14:26:41.837Z
See also http://cstheory.stackexchange.com/questions/1718/which-definition-of-asymptotic-growth-rate-should-we-teach for a related discussion of growth rates.
András Salamon
CC BY-SA 2.5
2011-03-22T17:57:54.357Z
@Wei: To most complexity theorists (see Lance below), your function is θ(n^2); to most algorithmists (see Knuth or CLRS), your function is Ο(n^2) and Ω(n).  Both notations are nearly, but not completely, standard in their subcommunities; to make things worse, these two subcommunities overlap heavily!  So if it matters which notation you use, you *must* say explicitly which notation you're using.  (Fortunately, it rarely matters.)
Jeffε
CC BY-SA 2.5
2011-03-26T07:37:50.137Z
@Jeffe . I believe you should post your comment as an answer.
chazisop
<cc.complexity-theory><time-complexity>
What is the "right" definition of upper and lower bounds?
Wei Yu
# What is the "right" definition of upper and lower bounds?

(Asked by: username_0 on 2011-03-19)

Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.

1. So, what is the lower bound of the problem? The way I understood it is just the lower bound of $f(n)$. But we know that $f(n) = \Omega(n^2)$ implies that there exists constant $k$, $n\_0$ such that for all $n > n\_0$, $f(n) > kn^2$, which is not true. Thus it seems that we can only say $f(n) = \Omega(n)$.
   But usually, we will call the problem has a lower bound of $\Omega(n^2)$, right?
2. Assuming that $g(n) = \Omega(n^2)$, which means that there exists constant $k$, $n\_0$ such that for all $n > n\_0$, $g(n) > kn^2$. Let's also assume a problem has running time $g(n)$. If we can reduce this problem for all the primes $n$ to another problem (with same input size), can we say the running time of the other problem has a lower bound of $\Omega(n^2)$?

**Tags:** cc.complexity-theory, time-complexity
> **Comments:**
> **username_1**: This is why mathematicians use lim sup and lim inf.  
> **username_0**: So I think I understand the difference. I think post people will just understand Omega as infinitely often.  But in case I want to make an explicit distinction, are there any notations I can use other than expanding it?  
> **username_1**: @Wei Yu: lim sup and lim inf. You say $$\limsup \frac{g(n)}{n^2} \geq k$$ for some constant $k$ if you want to  say that $g(n) \geq k n^2$ infinitely often, and  $$\liminf \frac{g(n)}{n^2} \geq k$$ if you want to say $g(n) \geq k n^2$ for all sufficiently large $n$. $$\ $$ Especially if you're talking to mathematicians.  
> **username_2**: See also http://cstheory.stackexchange.com/questions/1718/which-definition-of-asymptotic-growth-rate-should-we-teach for a related discussion of growth rates.  
> **username_3**: @Wei: To most complexity theorists (see Lance below), your function is θ(n^2); to most algorithmists (see Knuth or CLRS), your function is Ο(n^2) and Ω(n).  Both notations are nearly, but not completely, standard in their subcommunities; to make things worse, these two subcommunities overlap heavily!  So if it matters which notation you use, you *must* say explicitly which notation you're using.  (Fortunately, it rarely matters.)  
> **username_4**: @Jeffe . I believe you should post your comment as an answer.  

---

## 4 answers

### Answer by username_5 on 2011-03-19. Score: 13

The right definition of $f(n)=\Omega(n^2)$ is that there exists some $k>0$ such that for infinitely many $n$, $f(n)\geq kn^2$. The infinitely-often definition for lower bounds handles your issues and is how we use it in practice.

I did a [post](http://blog.computationalcomplexity.org/2005/01/big-omega.html) on this back in 2005.

Some textbooks get this definition right, some don't.

> **Comments:**
> **username_3**: Knuth disagrees with you: http://portal.acm.org/citation.cfm?id=1008329  
> **username_6**: CLRS and Wikipedia also disagree with you. The infinitey-often definition is a noteworthy alternative, but seems to be less widely used.  
> **username_7**: i think these definitions all agree when the set of exceptions is measure 0.  
> **username_2**: The problem with "infinitely often" definitions is that they don't usually exclude "infinitely often not".  So we have the horrible consequence that with this definition $f(n)=\Omega(n^2)$ but _also_ $f(n)=o(n+1)$, where the $\Omega$ and $o$ are meant to be strict orders in some sense.  I really dislike this.  At least @Carter's suggestion of measure 0 exceptions is a bit less horrible, while still allowing a finer order than the usual one.  
> **username_8**: @András: I don't follow. If you define $\Omega$ using this version (infinitely often) and $o$ as usual (for sufficiently large $n$), I don't see how you could have $f(n) = \Omega(n^2)$ and $f(n) = o(n+1)$.  
> **username_2**: @Jukka: If you define $\Omega$ this way then $o$ should probably be defined in a similar way?  
> **username_8**: @András: I don't think so. Has anyone ever used (or suggested) a similar definition of $o$ or $O$?  
> **username_2**: @Jukka: No, I'm misusing $o$ here.  As you hint I have to correct my argument to use $O$ instead of $o$.  Let me therefore restate the actual objection without using $o$ or $O$.  With "infinitely often", one has the anomaly that $n = \Omega(f(n))$, $f(n) = \Omega(n^2)$, yet $n \ne \Omega(n^2)$.  So $\Omega$ doesn't even form a preorder.  

---

### Answer by username_9 on 2011-03-25. Score: 4

With [Knuth](http://dx.doi.org/10.1145/1008328.1008329)'s definition you can assert only $f(n)\in\Omega(n)$. As
you observe, this is not intuitive and happens for functions [Vitányi and Meertens](http://dx.doi.org/10.1145/382242.382835) call "wild". They propose to define

$$\Omega(f(n))=\{ g \mid \exists \delta>0:\forall n\_0>0:\exists n>n\_0: g(n)\geq \delta f(n)\}\textrm{.}$$

(This is the same as Lance's definition.) With this definition $f(n)\in\Omega(n^2)$.


---

### Answer by username_10 on 2011-03-25. Score: 2

I think we should distinguish between two things:

* a lowerbound for a function
* a lowerbound for a problem (algorithm)

For functions, when we fix an order the definition of [lowerbound/upperbound](http://en.wikipedia.org/wiki/Lower_bound) follows from it. If the order relation is asymptotic [majorization](http://en.wikipedia.org/wiki/Majorization#In_recursion_theory) (ignoring constant factors)

$$f \preceq g : \exists c,n \forall m>n. \ f(x) \leq c g(x) $$

then the definition is the usual definition of $O$ and $\Omega$. Both of them are used extensively in other areas like combinatorics.

But when we talk about a lowerbound for a problem (an algorithm) what we really want to say is that the problem requires certain amount of resources (for running the algorithm solving the problem). Often the complexity classes are parametrized by functions like $\mathbf{Time}(t(n))$, and we simple say that the problem is lower bounded by a function, but this only works for nice functions (e.g. the running time of the algorithm is monotone, etc.). What we want to say in these cases is that we need $n^2$ running time to solve the problem, i.e. less than $n^2$ running time is not sufficient, which formally becomes Lance's definition that the running time of the algorithm is not in $o(t(n))$.


---

### Answer by username_4 on 2011-03-19. Score: 2

I don't know about the most widely used, but I believe I know of the oldest usage (for computer science anyway).

In the 1965 paper by Hartmanis & Stearns "On the computational complexity of algorithms", Corollary 2.1 is:

> If $U$ and $T$ are time-functions such that $\inf\_{n \rightarrow \infty} \frac{T(n)}{U(n)} \geq 0 $ then $S\_{U} \subseteq S\_{T}$

where $S\_{K}$ is the complexity class of all problems computable in $O( K(n) )$ . T(n) must obey $ T(n) \geq n/k$ for some integer $k$ and all $n$ and $T(n) \leq T(n+1)$ , but it doesn't have to be time-constructible.

Your function obeys the first rule for $k = 1$ but fails to obey the second rule.

Corollary 2.2 is the reciproral of the above and uses limit supremum, but still has these requirements. I guess as algorithms got more complex by the years, it is possible that the requirements have been relaxed.


---

