1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – apnorton Feb 12 '13 at 14:02
  • $\begingroup$ 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"? $\endgroup$ – tdenniston Feb 12 '13 at 14:11
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tdenniston Feb 12 '13 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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