4
$\begingroup$

I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063:

...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$...

How can the second inequality be possible since $n!$ is super-exponential and it grows always faster than $2^n$? Perhaps i'm making a too stupid mistake?

$\endgroup$
5
$\begingroup$

Descriptively

The standard convention is that

$$f(x) = O(g(x))$$

should really be interpreted as

$$f(x) \in O(g(x)),$$

as $O(g(x))$ is most properly viewed as a set of functions. Yes, that means the former notation is a bit sloppy. Personally, I don't like it much, but that's the accepted short-hand.

By the same token, the standard convention is that

$$f(x) = O(g(x)) = O(h(x))$$

actually means

$$f(x) \in O(g(x)) \subseteq O(h(x)).$$

The former notation is a bit sloppy (and I don't like), but that's the accepted short-hand notation.

Or, in this case,

$$O(f(x)) = O(g(x))$$

should be interpreted as

$$O(f(x)) \subseteq O(g(x)).$$

The same holds for $\Omega$, too.

Yes, this is sloppy and imprecise. I think it would be clearer if authors didn't use this notational short-hand. But, it's a standard notational convenience. Hopefully, once you're aware of this, it should be possible to work out what was intended from context.

Prescriptively

This use of notation is ugly and confusing and should be avoided, where ever possible.

$\endgroup$
4
$\begingroup$

This is where the abuse of notation "$f=\Omega(g)$" starts to turn into serious abuse. While I'm happy to write $f=\Omega(g)$1 in most contexts, as soon as you start talking about $\Omega(g)$ as a set, I think you're obliged to start using proper set notation. While we agree (some of us under duress) that $=$ can mean "is a member of" when it's written between a function and an asymptotic class, $=$ written between two sets just means equality, damnit, leading to exactly the confusion causing this question.

The equation you quoted should has been written something like $$f\in \Omega(m!) \subseteq \Omega(\sqrt{n}!) \subset \Omega(2^{\sqrt{n}})\,.$$ (Exactly what the "$\subseteq$" should be depends on the actual relationship between $m$ and $n$, which isn't stated in the question. But $\subseteq$ had better be true because, if it isn't, the reasoning seems to be flawed.)

Alternatively, it could be split into something like, "$f=\Omega(m!)$, which gives us $f=\Omega(\sqrt{n}!)$ and, therefore, $f=\Omega(2^{\sqrt{n}})$." This maintains the standard abuse of notation but avoids writing $=$ between two sets that are manifestly not equal.


1 For example, taking "$O(g)$" to mean "some function in the set $O(g)$" allows one to write things like "$f(x) = x^2 + O(x)$" to bound error terms.

$\endgroup$
0
$\begingroup$

Ω(f(n)) represents a set of functions. In this case the equality doesn't mean that the sets are the same, but that all three apply to the runtime. (The sets aren't actually equal)

$\endgroup$
  • $\begingroup$ Just like i said "I'm making a too stupid mistake": in fact i confused $\Omega$ with $\Theta$... Now it's clear that the relation is ok since $\Omega$ is about lower bound: $\Omega(g(n))=\{f(n): \exists c,n_0, 0\leq cg(n)\leq f(n), \forall\ n>n_0\}$ $\endgroup$ – Leo Jun 15 '16 at 9:11
  • $\begingroup$ BTW, I think the equal sign should be interpreted as $\subset$, just as in $n^2=\Omega(n)$, mentioned in the same book, page 49. $\endgroup$ – Leo Jun 15 '16 at 9:16
  • $\begingroup$ @Leo I agree that in the "equation" in your question, the equals sign should be interpreted as $\subset$ or $\subseteq$ but the equals sign in "$n^2=\Omega(n)$" means $\in$, not $\subset$. (Probably just a brainfart on your part but I thought I'd mention it just in case it was a real misunderstanding.) $\endgroup$ – David Richerby Jun 15 '16 at 11:02
  • $\begingroup$ You are right, it should be $\in$ $\endgroup$ – Leo Jun 15 '16 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.