Equivalent definitions of big O

Question

Let $A = \{ g(n) \mid \exists c,n_0 \, \forall n \ge n_0\colon g(n) \le cf(n) \}$, and $B = \{ g(n) \mid \exists c,n_0 \, \forall n \geq n_0 \colon g(n) < cf(n) \}$.

Prove $A = B$.

My solution:

• Let $f(n)$ and $g(n)$ be functions from $\mathbb{N}$ to $\mathbb{N}$.
• $g(n)\le cf(n)$ for all $n > n_0$.
• $g(n) = O(f(n))$ means $\exists c, n_0 \forall n\colon n > n_0 \Rightarrow g(n) \le cf(n)$.
• To prove A, choose values for $c$ and $n_0$ and prove that $n > n_0$ implies $g(n) \le cf(n)$.
• Choose $n_0 = 1$.
• Assuming $n>1$, find a $c$ such that $g(n)/f(n) \le cf(n)/f(n) = c$.
• This shows that $n>1$ implies $g(n)\le cf(n)$.
• $n>1$ implies $1<n$, $n<n^2$, $n^2<n^3$, and so on.

My problem: Given an equation I know how to get $c$ and $n_0$. But now given the definition, how can I prove that there exist $c$ and $n_0$ in that big O definition in order to get the result A=B?

Answer 1

Clearly, $B \subseteq A$, since $\lt$ implies $\le$.

Assuming that $f(n)$, $g(n)$ and $c$ are always positive,

If $g(n) \le c f(n)$, then $g(n) \lt (c + 1) f(n)$.

So, if we can find a $c$ that satisfies $A$, we can find one that satisfies $B$.

It follows that $A \subseteq B$, hence that $A = B$.