3

Given two functions $f(n)$ and $g(n)$, is it possible that $f(n) = O(g)$ and that $g(n) = O(f)$?

If the answer is yes, I have a follow-up: if $f(n)$ and $g(n)$ are Big-O of each other, does that also mean that they are Big-Omega of each other? Because if that is the case, that would mean that they are also Big-Theta of each other.

UnworthyToast
  • 259
  • 2
    The relation $f=O(g)$ behaves like $x\le y$. In particular, $f=O(f)$. – anon Jul 19 '16 at 23:42
  • To address the second point: yes. If $f=O(g)$ and $g=O(f)$, then (you can check with the definitions) $f=\Omega(g)$ and $g=\Omega(f)$, and overall $f=\Theta(g)$. – Clement C. Jul 19 '16 at 23:48
  • Hi, UnworthyToast. After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $\color{green}\checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?. – Clement C. Jul 29 '16 at 14:20

3 Answers3

5

Can two function be Big-O of each other?

The answer is yes.

One may take $f(n)=n$ and $g(n)=2n+1$, as $ n \to \infty$, one has $$ \left|\frac{f(n)}{g(n)}\right|=\frac{n}{2n+1}\le \frac12 \implies f=O(g) $$ and $$ \left|\frac{g(n)}{f(n)}\right|=\frac{2n+1}{n}\le 3 \implies g=O(f). $$

Olivier Oloa
  • 120,989
2

Is it possible? Yes. A simple example: $f=g$.

What does it imply? This is equivalent to saying that $f=\Theta(g)$. To see why:

If $f=O(g)$, there exists $c>0$ and $N \geq 0$ such that $$ \forall n \geq N, \qquad f(n) \leq c\cdot g(n) \tag{1} $$

If $g=O(f)$, there exists $c'>0$ and $N' \geq 0$ such that $$ \forall n \geq N', \qquad g(n) \leq c'\cdot f(n) \tag{2} $$

Combining (1) and (2), and choosing $M\stackrel{\rm def}{=}\max(N,N')$, $\alpha\stackrel{\rm def}{=}\frac{1}{c} > 0$, $\beta \stackrel{\rm def}{=} c'$, we get that there exist $M\geq 0$, constants $\alpha,\beta>0$ such that $$ \forall n \geq M, \qquad \alpha f(n) \leq g(n) \leq \beta f(n) \tag{3} $$ which by definition means $f=\Theta(g)$. This should answer both your questions.

Clement C.
  • 67,323
0

The following are equivalent:

  1. $f(n) = O(g(n))$ and $g(n) = O(f(n))$
  2. $f(n) = \Omega(g(n))$ and $g(n) = \Omega(f(n))$ (using the definition from computational complexity theory, not the one from analytic number theory)
  3. $f(n) = \Theta(g(n))$.
Robert Israel
  • 448,999