Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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 '13 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 '13 at 14:11

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 '13 at 14:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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