# Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?

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?

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

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.

Ω(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)

• 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\}$ – Leo Jun 15 '16 at 9:11
• 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. – Leo Jun 15 '16 at 9:16
• @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.) – David Richerby Jun 15 '16 at 11:02
• You are right, it should be $\in$ – Leo Jun 15 '16 at 12:12