2

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.

Tim Post
  • 33,371
  • 15
  • 110
  • 174
Vlad Schnakovszki
  • 8,434
  • 6
  • 80
  • 114
  • 2
    What, in English, is `f = Ω(g)` saying? If you "translate" these to English, there's a simple relationship between `Ω` and `O` This may help: http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations - specifically the "informal definition" column... – SubSevn May 23 '13 at 14:18
  • f = Ω(g) means "f is bounded below by g asymptotically". f = O(g) means "f is bounded above by g asymptotically". I was thinking d might be the correct answer but really needed a confirmation. If d is indeed the answer, post this as an answer so I can mark it. Thanks. – Vlad Schnakovszki May 23 '13 at 14:23
  • I have added it as an answer. – SubSevn May 23 '13 at 14:30

1 Answers1

4

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

SubSevn
  • 1,008
  • 2
  • 10
  • 27