Big Omega notation - what is f = Ω(g)?

问题:

I've been trying for the better part of an hour to find reference to the following:

f = Ω(g)

But I have had no luck at all. I need to answer a question for an assignment and I can't find references.

The assignment is basically asking me to indicate what it (f = Ω(g)) means, in the context of the following choices:

1. f = Ω(g(n))
2. g = o(ln n)
3. g = o(g(n))
4. g = O(f)
5. f = O(g)

Initially, I thought that perhaps there is an error in the question.

I know option 1 is wrong and assume option 5 is also wrong, but after an hour online I couldn't figure out which one is the answer.

Can someone please explain to me how to figure this out? I realize that might mean giving me the answer so it can be explained, but I'm more interested in why one of these answers are correct.

回答1:

"f = Ω(g) means "f is bounded below by g asymptotically". f = O(g) means "f is bounded above by g asymptotically" as per the comments.

If a river's upper bound is a bridge, what's a bridge's lower bound? The river.

I would suggest d

(For completeness, the "little" versions of these imply a very strong difference in growth.)