0
$\begingroup$

I don't understand the proof of below sentences.

  1. $O(f(n))=O(g(n)) \iff \Omega(f(n))=\Omega(g(n)) \iff \theta(f(n))=\theta(g(n))$

  2. $f(n)=\theta(g(n)) \iff g(n)=\theta(f(n))$

How can I prove these statements?

$\endgroup$
8
  • 2
    $\begingroup$ You say you don't understand the proofs of the given sentences, but since you haven't given us the proofs, it is hard to help you with them. $\endgroup$ Apr 15, 2018 at 10:41
  • 1
    $\begingroup$ All statements you quote are true, and so there aren't any "non-proving examples". $\endgroup$ Apr 15, 2018 at 10:42
  • $\begingroup$ Can you prove or give some link? I cannot find the proof link. $\endgroup$
    – molamola
    Apr 15, 2018 at 11:06
  • $\begingroup$ We can't help you to understand a proof unless you tell us what the proof is. $\endgroup$ Apr 15, 2018 at 11:07
  • 1
    $\begingroup$ Also, you pose two different problems in one question; please don't do that. $\endgroup$
    – Raphael
    Apr 15, 2018 at 19:30

1 Answer 1

0
$\begingroup$

We will be using the following definitions:

Let $f\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ be a function mapping positive integers to positive integers.

The class $O(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C>0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \leq Cf(n)$.

The class $\Omega(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $c>0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \geq cf(n)$.

The class $\Theta(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C,c>0$, for all $n \in \mathbb{Z}_+$ we have $cf(n) \leq g(n) \leq Cf(n)$.

We also write $g(n) = O(f(n))$ instead of $g(n) \in O(f(n))$, and similarly for the other two.

These are equivalent to the more standard definition in which the above only has to hold for large enough $n$. You can also carry out the proofs below using the standard definitions — this entails only small changes.

Let's start with the second statement: $f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$.

Suppose that $f(n) = \Theta(g(n))$. Then there exist $C,c>0$ such that for all $n$ we have $cf(n) \leq g(n) \leq Cf(n)$. Therefore for all $n$ we have $C^{-1} g(n) \leq f(n) \leq c^{-1} g(n)$, and so $g(n) = \Theta(f(n))$. Similarly, if $g(n) = \Theta(f(n))$ then $f(n) = \Theta(g(n))$.

Now let us go back to the first statement: $O(f(n)) = O(g(n))$ iff $\Omega(f(n)) = \Omega(g(n))$ iff $\Theta(f(n)) = \Theta(g(n))$.

Suppose that $O(f(n)) = O(g(n))$. It is easy to check that $g(n) = O(g(n))$ (take $C = 1$), and so $O(f(n)) = O(g(n))$ implies that $g(n) = O(f(n))$. That is, there exists $D>0$ such that $g(n) \leq Df(n)$ for all $n$. Similarly, $f(n) = O(g(n))$, and so there exists $E>0$ such that $f(n) \leq Eg(n)$ for all $n$. Suppose now that $h(n) = \Theta(f(n))$. Then there exist $C,c>0$ such that $cf(n) \leq h(n) \leq Cf(n)$ for all $n$. This implies that $cD^{-1} g(n) \leq h(n) \leq CEg(n)$, and so $h(n) = \Theta(g(n))$. Similarly, if $h(n) = \Theta(g(n))$ then $h(n) = \Theta(f(n))$, and so $\Theta(f(n)) = \Theta(g(n))$.

Similarly, if $\Omega(f(n)) = \Omega(g(n))$ then $\Theta(f(n)) = \Theta(g(n))$.

Conversely, if $\Theta(f(n)) = \Theta(g(n))$ then, as before, $f(n) = \Theta(g(n))$. This means that there exist $C,c>0$ such that $cg(n) \leq f(n) \leq Cg(n)$ for all $n$. Now suppose that $h(n) = O(f(n))$. Then there exists $D>0$ such that $h(n) \leq Df(n)$ for all $n$. Since $h(n) \leq Df(n) \leq DCg(n)$, we see that $h(n) = O(g(n))$. Similarly, if $h(n) = O(g(n))$ then there exists $E>0$ such that $h(n) \leq Eg(n)$. This implies that $h(n) \leq Ec^{-1} f(n)$, and so $h(n) = O(f(n))$. Thus $O(g(n)) = O(f(n))$. Similarly, $\Omega(g(n)) = \Omega(f(n))$.

$\endgroup$
3
  • $\begingroup$ It is so excellent proof I have ever seen!! But I didn't understand very trivial statement $cf(n) \le g(n) \le Cf(n)$ implies $C^{-1}g(n) \le f(n) \le c^{-1}g(n)$. Can you explain? $\endgroup$
    – molamola
    Apr 15, 2018 at 11:52
  • $\begingroup$ This is just elementary arithmetic. If you stare at it hard enough, you'll eventually get it. $\endgroup$ Apr 15, 2018 at 11:56
  • $\begingroup$ Ok. sorry for my ignorance. Thank you for spending your time with me!! $\endgroup$
    – molamola
    Apr 15, 2018 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.