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

Dave Clarke
  • 16,666
  • 3
  • 60
  • 106
Wei Yu
  • 331
  • 2
  • 3
  • 12
    This is why mathematicians use lim sup and lim inf. – Peter Shor Mar 19 '11 at 14:02
  • 1
    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 Mar 19 '11 at 18:17
  • 4
    @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 Mar 19 '11 at 18:30
  • 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 Mar 20 '11 at 14:26
  • 12
    @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ε Mar 22 '11 at 17:57
  • 2
    @Jeffe . I believe you should post your comment as an answer. – chazisop Mar 26 '11 at 07:37

4 Answers4

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 on this back in 2005.

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

Lance Fortnow
  • 8,681
  • 44
  • 59
  • 14
    Knuth disagrees with you: http://portal.acm.org/citation.cfm?id=1008329 – Jeffε Mar 19 '11 at 15:32
  • 4
    CLRS and Wikipedia also disagree with you. The infinitey-often definition is a noteworthy alternative, but seems to be less widely used. – Anonymous Mar 19 '11 at 16:22
  • i think these definitions all agree when the set of exceptions is measure 0. – Carter Tazio Schonwald Mar 22 '11 at 22:16
  • 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. – András Salamon Mar 25 '11 at 15:26
  • @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 Mar 26 '11 at 18:34
  • @Jukka: If you define $\Omega$ this way then $o$ should probably be defined in a similar way? – András Salamon Mar 26 '11 at 23:38
  • @András: I don't think so. Has anyone ever used (or suggested) a similar definition of $o$ or $O$? – Jukka Suomela Mar 27 '11 at 08:14
  • 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. – András Salamon Mar 27 '11 at 16:34
4

With Knuth'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 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)$.

Marcus Ritt
  • 1,450
  • 14
  • 21
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.

chazisop
  • 3,796
  • 2
  • 29
  • 37
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 follows from it. If the order relation is asymptotic majorization (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))$.

Kaveh
  • 21,577
  • 8
  • 82
  • 183