If f ≠ ω(g), does f = O(g)?

I'm stuck proving or disproving this statement:

If f ≠ ω(g), then f = O(g)

Intuitively, I think that the statement is false, however, I can't figure out a valid counterexample.

My thought is that we know that f is not bounded from below by a function of g, but that tells us nothing about an upper bound.

Any thoughts? Hints in the right direction?

---

As a hint, this statement is false. Think about two functions that oscillate back and forth, where each function overtakes the other over and over again. That would make f ≠ ω(g), because f is repeatedly dominated by g, and would make f ≠ O(g) because f repeatedly dominates g.

You'll need to find concrete choices of f and g that make this work and formally establish that f ≠ ω(g) and f ≠ O(g) to formalize this, and I'll leave that as an exercise.

Hope this helps!

链接地址: http://www.djcxy.com/p/39898.html

上一篇: 从整数流创建最大堆

下一篇: 如果f≠ω（g），那么f = O（g）？