patternMinor
Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?
Viewed 0 times
sqrtomegacorrect
Problem
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?
...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?
Solution
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.
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.
Context
StackExchange Computer Science Q#59664, answer score: 5
Revisions (0)
No revisions yet.