Question

Show that if \(f\left( x \right)\) and \(g\left( x \right)\)are functions from the set of real numbers to the set of real numbers, then \(f\left( x \right)\) is \(O\left( {g\left( x \right)} \right)\) if and only if \(g\left( x \right)\) is \(\Omega \left( {f\left( x \right)} \right)\).

Short answer

The \(f(x)\) is \(O\left( {g\left( x \right)} \right)\) if and only if \(g(x)\) is \(\Omega \left( {g\left( x \right)} \right)\) proved by using definitions of Big-O Notation, Big-Omega Notation, and Big-Theta Notation.

Step-by-step solution

Write the explanation.

Given:\(f:R \to R\)and\(g:R \to R\)

We have to show that\(f(x)\)is\(O\left( {g\left( x \right)} \right)\)if and only if\(g(x)\)is\(\Omega \left( {g\left( x \right)} \right)\).

Big-O Notation:Let the real or complex values function is\(f\)and real valued function is\(g\). Then\(f\left( x \right)\)is\(O\left( {g\left( x \right)} \right)\). When there exists a positive real number\(M\)and real number\(k\)such that\(\left| {\left. {f\left( x \right)} \right|} \right. \ge M\left| {\left. {g\left( x \right)} \right|} \right.\forall x > k,\)where\(M\)and\(k\)are not unique.

Big-Omega Notation:Let the real or complex values function is\(f\)and real valued function is\(g\). Then\(f\left( x \right)\)is\(\Omega \left( {g\left( x \right)} \right)\). When there exists a positive real number\(M\)and real number\(k\)such that\(\left| {\left. {f\left( x \right)} \right|} \right. \ge M\left| {\left. {g\left( x \right)} \right|} \right.\forall x > k,\)where\(M\)and\(k\)are not unique.

Big-Theta Notation: If \(f\left( x \right)\) is \(O\left( {g\left( x \right)} \right)\) and \(f\left( x \right)\) is \(\Omega \left( {g\left( x \right)} \right)\), then \(f\left( x \right)\) is \(\Theta \left( {g\left( x \right)} \right)\). So, we can conclude that \(f\) has the same order as \(g\).

Show that \(g\left( x \right)\) is \(\Omega \left( {f\left( x \right)} \right)\).

Let\(f\left( x \right)\)is\(O\left( {g\left( x \right)} \right)\).

So, by the definition of Big-O notation we have:

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. \le M\left| {\left. {g\left( x \right)} \right|} \right.\forall x > k\\\frac{1}{M}\left| {\left. {f\left( x \right)} \right|} \right. \le \left| {\left. {g\left( x \right)} \right|} \right.\forall x > k\end{aligned}\)

Let\({M_1} = \frac{1}{M}\), then we have\({M_1}\left| {\left. {f\left( x \right)} \right|} \right. \le \left| {\left. {g\left( x \right)} \right|} \right.\forall x > k\)

Therefore, by definition of Big-Omega notation, we have\(g\left( x \right)\)is\(\Omega \left( {f\left( x \right)} \right)\)with\(k\)and\({M_1} = \frac{1}{M}\)

Hence proved that \(g\left( x \right)\) is \(\Omega \left( {f\left( x \right)} \right)\).

Show that \(f\left( x \right)\) is \(O\left( {g\left( x \right)} \right)\).

Similarly,

Let\(g\left( x \right)\)is\(\Omega \left( {f\left( x \right)} \right)\)and\(g\left( x \right)\)is\(O\left( {f\left( x \right)} \right)\).

By the definition of Big-Omega notation we have:

\(\left| {\left. {f\left( x \right)} \right|} \right. \le M\left| {\left. {g\left( x \right)} \right|} \right.\forall x > k\)and

\(\left| {\left. {f\left( x \right)} \right|} \right. \le \frac{1}{M}\left| {\left. {f\left( x \right)} \right|} \right.\forall x > k\)

Let\({M_1} = \frac{1}{M}\), then we have \(\left| {\left. {f\left( x \right)} \right|} \right. \le {M_1}\left| {\left. {g\left( x \right)} \right|} \right.\forall x > k\)

Hence, by definition of Big-O notation\(f\left( x \right)\)is\(\Omega \left( {g\left( x \right)} \right)\)with\(k\)and\({M_1} = \frac{1}{M}\)

Hence proved that\(f\left( x \right)\)is\(O\left( {f\left( x \right)} \right)\).

And also proved that\(f(x)\)is\(O\left( {g\left( x \right)} \right)\)if and only if\(g(x)\)is\(\Omega \left( {g\left( x \right)} \right)\).