Complexity and logic question - natural numbers $c$ and $d$ such that $f(n) ≤ c · g(n) + d$ from $f ∈ O(g)$

Question

I was working through some problems and got stuck on this question, was hoping for some help.

Show that whenever $f\in O(g)$, there are natural numbers $c$ and $d$ such that $f(n)\leq c\cdot g(n) + d$ for all natural numbers $n$.

Answer 1

Okay this is a good question, to answer it we need to get down to what $f \in O(g)$ really means by definition. I'm going to assume given the context of this question, that $f,g:\mathbb{N}\rightarrow \mathbb{N}$, feel free to correct me lol.

If $f\in O(g)$ then by definition $\implies \exists N,c\in \mathbb{N}$ such that whenever $n>N$, $\frac{f(n)}{g(n)}\leq c$

Hence given $n>N$, we have $f(n) \leq c\cdot g(n)$

But WAIT you are saying what about $+d$, well this comes from considering $n<N$, since after all we want this inequality to hold $\forall n\in \mathbb{N}$

For $n<N$, assuming $f$ is bounded over $n<N$, (a fair assumption for this question), $f(n) \leq max(\{f(n)|n<N\})$. Trivially let $d = max(\{f(n)|n<N\})$

$$\implies f(n) \leq d, \forall n<N$$

Hence $\forall n\in \mathbb{N}$, $f(n) \leq c\cdot g(n) + d$

$$\square$$