Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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)
