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

2019-07-21 07:13发布

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条回答
祖国的老花朵
2楼-- · 2019-07-21 07:58

"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.)

查看更多
登录 后发表回答