Two different definitions of big O notation

Question

I find there are two different definitions of big O notations for $f(n)=O(g(n))$ as $n\rightarrow\infty$:

1. There exist $M>0$, and $N\in\mathbb{N}$, such that $|f(n)|\leq M|g(n)|$ for $n\geq N$.
2. There exist $M>0$, such that $|f(n)|\leq M|g(n)|$ for $n\in\mathbb{N}$.

I do not which one is right or when two of them is equivalent.

Answer 1

Under some (pretty weak) condition, the two are equivalent.

Clearly the second definition implies the first.

Now assume the first definition; we show that this implies the second whenever either of the following conditions hold:

• (a) $g$ is nonzero at all the positive integers less than $n$,
• (b) $f(k)=0$ whenever $g(k)=0$ and $k<n$.

In case (a), let $$M^{\prime} = \max\left\{\frac{|f(1)|}{|g(1)|},\frac{|f(2)|}{|g(2)|},\ldots,\frac{|f(n-1)|}{|g(n-1)|},M\right\}.$$ In the case (b), adjust the choice of $M^{\prime}$ to "miss out" the undefined values. Either way, it follows that $|f(n)|\leq M^{\prime}|g(n)|$ for all $n\in\mathbb{N}$, thus proving the second definition.

I'll admit that I'm actually unsure if this can be improved upon, but I highly doubt it can in general; and, after all, since we are taking the limit $n\to\infty$, we probably don't care about what $f$ and $g$ do for small values anyway.