I learned in my Algorithmics course that that :
$f(n) \in O(g(n))$ can be written as $f(n) \leq cg(n)$. My confusion is about what $c$ is. Is it a constant that can be any value? Is it a constant that can be changed depending on which value of $f(n)$ or is it a value that must make the inequality hold true for every f(n) and g(n).
It should read something like:
$f(n)=\mathcal{O}(g(n))$ (or $\in$) if there exists a positive constant $c$ and natural number $N$, such that for all $n\ge N$, $f(n)\le cg(n)$. That is, $c$ does not depend on $n$.
There are slightly varying definitions, such as $|f(n)|$ replacing $f(n)$, and another definition based on limits.
