Big Omega Designation - What is f = Ω (g)?

I have been trying for most of the hour to find a link to the following:

f = Ω (g)

But I’m not lucky at all. I need to answer a question about an assignment, and I cannot find the links.

The assignment basically asks me to indicate what this means ( f = Ω(g) ), in the context of the following options:

  • f = Ω (g (n))
  • g = o (ln n)
  • g = o (g (n))
  • g = O (f)
  • f = O (g)

Initially, I thought there might be a mistake in the question.

I know that option 1 is wrong, and suppose option 5 is also wrong, but after an hour on the net I couldn’t figure out which one is the answer.

Can someone please explain to me how to understand this? I understand that this could give me an answer so that it can be explained, but I'm more interested in why one of these answers is correct.

+2
complexity-theory big-o
source share
1 answer

f = Ω(g) means that“ f is bounded from below by g asymptotically. ” f = O(g) means that“ f is bounded from above by g asymptotically ”according to the comments.

If the upper boundary of the river is a bridge, which bridge is lower? River.

I would suggest d

(For completeness, the "small" versions of them imply a very large difference in height.)

+3
source share

All Articles