# Proving Big-$\Theta$ if and only if Big-$O$ and Big-$\Omega$

Given the definitions of Big-$O$ and Big-$\Omega$, I'd like to prove that $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.

Here's what I've come up with, but I'm not sure it's a rigorous proof, or even correct. I'm looking for comments on both the structure and style of my proof as well as correctness.

Proof by contradiction.

Suppose $f(n) = \Theta(g(n))$ and either $f(n) \ne O(g(n))$ or $f(n) \ne \Omega(g(n))$.

By the definition of $\Theta$,

$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$

For some positive constants $c_1$, $c_2$, and $n > n_0$.

But it was given that $f(n) \ne O(g(n))$, which means there exist no positive constants $c$, $n_0$ such that for all $n>n_0$,

$0 \le f(n) \le c \cdot g(n)$

Which is a contradiction. $\blacksquare$

-

But it wasn't given that $f(n) \ne O(g(n))$, but rather that $f(n) \ne O(g(n)) \vee f(n) \ne \Omega(n)$ – anorton Feb 12 at 14:02
Could I revise my supposition to be "Suppose $f(n)=\Theta(g(n))$ and $f(n) \ne O(g(n))$"? Is that enough to contradict "if and only if"? – proc-self-maps Feb 12 at 14:11

## 1 Answer

To prove an if and only if statement, you must prove that $p \to q$ and $q\to p$. Applied to your statement, you must prove that: $$f(n) = \Theta(g(n)) \implies f(n) = \mathcal{O}(g(n)) \wedge f(n)=\Omega(g(n)) \tag{1}$$ ...and... $$f(n) = \mathcal{O}(g(n)) \wedge f(n)=\Omega(g(n))\implies f(n) = \Theta(g(n)) \tag{2}$$

Your proof only deals with the second case, and is therefore incomplete.

Also, I must ask, why did you go with a proof by contradiction for part 1? It appears that a direct proof would suffice:

Let $f$ and $g$ be functions, such that $f(n) = \Theta(g(n))$.

By definition of $\Theta$, there exist positive constants $k_1$ and $k_2$ such that, for sufficiently large $n$: $$k_1\cdot |g(n)| \le |f(n)| \le k_2\cdot |g(n)|$$

Thus, for sufficiently large $n$: $$|f(n)| \le k_2|g(n)|$$ Therefore $f(n) = \mathcal{O}(g(n))$ by definition.

And, for sufficiently large $n$: $$k_1|g(n)| \le |f(n)|$$ Therefore $f(n) = \Omega(g(n))$ by definition. $$\blacksquare$$

Still, part 2 needs to be proven for it to be an if and only if.

-

Exactly the kind of feedback I was looking for! Thanks. As for why I chose contradiction, I am unpracticed and a novice with proofs; proofs by contradiction are all I remember how to do from my undergraduate years. – proc-self-maps Feb 12 at 14:40
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 39, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9606947302818298, "perplexity_flag": "head"}