Constant value in definition of Big-O notation

Question

Most definitions of Big-O notation I've seen look like the following one:

$f(n) = O(g(n))$ means that there are positive constants $c$ and $k$, such that $f(n) \leq c \cdot g(n)$ for all $ n \geq k$.

I can't understand why saying that some $c$ has to exist and why we can't simply say that $f(n) \leq g(n)$, instead of $f(n) \leq c \cdot g(n)$. Overall, if one function dominates another (in this case the dominating one is $g(n)$), there's always a point above which $g(n)$ surpasses $f(x)$.

So my question is - is it really required to mention existence of constant $c$? If yes, why is that? If no, why do people do that?

Answer 1

One needs the $c$ so that $f(n)$ is big $O$ of any multiple of itself. If we were to drop the requirement for the existence of a $c$, we would have that $2n^2 \ne O(n^2)$, for example.

When I say $f$ is Big-$O$ of $g$, I'm saying the growth rate of $f$ is less than or equal to the growth rate of $g$.

It is worth mentioning that there is the closely related little-$o$ notation where $f(n) = o(g(n))$ if for every $c>0$ there exists $k \in \mathbb{N}$ such that $|f(n)| \le c \cdot |g(n)|$ for every $n \ge k$. In this case the growth rate of $g$ must truly dominate $f$

Answer 2

A big part of Big Oh is identifying what matters. The key growth information of the function $3x$ is the $x$, which is why $3x \in O(x)$. Note however that $3x > x$ for all positive $x$.