1

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?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Connal Sumlin
  • 41
  • 6
  • I googled "little o vs big o" and this was the first result. http://stackoverflow.com/a/1364491/2420979 – Haney Sep 17 '14 at 00:09
  • 1
    @Haney - I believe James is asking about Omega and O (subtly different concepts) - ie similar to http://en.wikipedia.org/wiki/Big_O_notation#The_Hardy.E2.80.93Littlewood_definition ? – David E Sep 17 '14 at 00:11
  • Look here http://cs.stackexchange.com/questions/1780/are-the-functions-always-asymptotically-comparable – Nuri Tasdemir Sep 17 '14 at 00:16
  • 1
    Yes, I was asking about little omega and Big O, however the table on the page Haney linked lead me to a conclusion. Thanks guys. – Connal Sumlin Sep 17 '14 at 00:19
  • Today I learned there's a little omega and a little o. Hah! Thanks for teaching me, all! – Haney Sep 17 '14 at 00:20

1 Answers1

3

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • So, you could let f(n) = sin(n) and let g(n) = cos(n) for your counterexample? And vice versa? – Connal Sumlin Sep 17 '14 at 00:30
  • Sorry to jump in here, but just wanted to say thanks templatetypedef for the correction to my clearly stupid post! I'm too tired to focus tonight and misread the definitions aha. – David E Sep 17 '14 at 00:37
  • Where "dominates" means f/g gets arbitrarily large, and not just f>g. – Teepeemm Sep 17 '14 at 00:45
  • @JamesSumlin `sin(n)` and `cos(n)` would work, but with `sin` and `cos`, it might be a little trickier to prove `f ∉ O(g)` if we're restricting `n` to integers (as `sin(n)`, `cos(n)` aren't particularly nice). You might find it easier with `sin(πn/2), cos(πn/2)`, or, if you have to have the functions taking values on the positive integers, you may have to think a little more creatively, to ensure f/g and g/f both can get arbitrarily large :) - hint: just tell your functions to take certain values on certain types of number... creating your own function is often the best approach in these qs :) – David E Sep 17 '14 at 00:46