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?