Leveraging the Proof by Contradiction Technique

We have talked at length about the big-O notation. We now want to go over how to convince ourselves that a particular function $f(n)$ is not $O(g(n))$.

The difficulty

Suppose our friend claims that $9^n\text{ is not }O(3^n)$. How can we be sure that our friend is right?

It’s not enough to come up with two choices for the constants $c^\prime$ and $n^\prime$ (constants in the big-O notation) because we actually need to show that no such constants exist. How do we show nonexistence?

It so happens that there’s a useful proof technique that’s very effective when applied to situations just like these.

The technique

The proof by contradiction technique is an indirect way to prove a point.

Suppose we want to show that “X is true.” We start by assuming the opposite of what we want to show. So, our starting assumption, in this case, would be “X is false.”

Then, we exercise our reason and make logical inferences until we arrive at a fact that contradicts another fact. Two contradictory facts indicate something went wrong. If our argument is valid, and every step logically follows from the previous steps, the only thing that could have possibly led to the contradiction is our starting assumption because that’s something we just made up. So, the only logical conclusion is that our starting assumption is false, implying for our above example that “X is true,” which is really what we wanted to show in the first place!

Example

Let’s apply this to the claim made by our friend.

Claim: $9^n$ ...