Big-O notation 1/O(n) = Omega(n)

I have received the assignment to prove 1/O(n) = Ω(n)

However, this would mean that n element of O(n) => 1/n element of Ω(n) which is clearly wrong.开发者_StackOverflow中文版

So my question is: Is the statement 1/O(n) = Ω(n) correct?

EDIT: I send an Email to the assistant who wrote the questions. And used the example of f(n) = 1. He then said, that the statement is indeed incorrect.

The notation 1/O(n) = Ω(n) is a bit vague. There is really no O(n) on it's own, there is only f(n) ~ O(n), which is a statement about values of function f (there is a constant C so that f(n) < Cn for each n).

And the statement to prove, if I understand it correctly, is "if function f(n) is O(n) than 1/f(n) is Ω(n)", formally:

f(n) ~ O(n) => 1/f(n) ~ Ω(n)

Edit: Except I don't think I understand it correctly, because f(n) = 1 ~ O(n), but 1/f(n) = f(n) = 1 is clearly isn't Ω(n). Weren't the assignment f(n) ~ O(n) => 1/f(n) ~ Ω(1/n) instead?

Edit: Different people tend to use different operators. Most common is f(n) = O(n), but that is confusing because the right hand side is not a function, so it can't be normal equality. We usually used f(n) ~ O(n) in school, which is less confusing, but still inconsistent with common use of that operator for general equivalence relations. Most consistent operator would be f(n) ∈ O(n), because the right hand side can reasonably be treated as set of functions.

O(n) more or less implies the following, for some polynomial function f(x), some polynomial function g(x) and O(f(x)):
In terms of magnitude, we have |f(x)| <= M|g(x)|, for some M. Basically, f is bounded above by a constant times g.

Ω(n) implies that, for some polynomial h(x), some polynomial k(x) and Ω(h(x)):
In terms of magnitude, |h(x)| >= M|k(x)|, for some M. Basically, h is bounded below by a constant times k.

So, for (O(f(x)))^-1, 1/|f(x)| <= 1/(M|g(x)|). A bit of re-arranging gives M|g(x)| <= |f(x)| - i.e. f(x) is bounded below by a constant times g, which is exactly the same as our definition for Ω(n) above.

It's a tad scratchy to be a formal proof, but it should get you started.