What is the constant $C$ in the definition of asymptotic notations?
The basic idea of asymptotic notation is that "constant factors shouldn't matter". This has several different interpretations. Taking as our example big O, the simplest interpretation is:


  For all $C,D&gt;0$ and functions $f,g$: $$ f = O(g) \Longleftrightarrow Cf = O(Dg). $$


This means that big O should be scale-invariant, that is, it should treat the functions $f$ and $Cf$ exactly the same. Stated differently, if $f_1,f_2$ differ by a constant factor, then $f_1,f_2$ should be treated the same.

In practice, the condition "$f_1/f_2=\text{const}$" is too restrictive. Instead, we would like to treat two functions $f_1,f_2$ in the same way as long as $f_1/f_2$ is bounded, that is, as long as $C_1 \leq f_1/f_2 \leq C_2$ for some constants $C_1,C_2&gt;0$. That is, we would like that


  For all $C_1,C_2,D_1,D_2$ and functions $f_1,f_2,g_1,g_2$ satisfying
  $C_1 \leq f_1/f_2 \leq C_2$ and $D_1 \leq g_1/g_2 \leq D_2$:
  $$
f_1 = O(g_1) \Longleftrightarrow f_2 = O(g_2).
$$


You can check that the definition of big O satisfies this invariance property. The constant in the definition of big O ensures that. Indeed, while $2n \leq n$ doesn't hold, $2n = O(n)$ does hold.

The integer constant – $N_0$ – in the definition of big O isn't really necessary. It is there so we can accommodate functions which aren't positive or aren't even defined for small $n$. If your functions aren't pathological in that sense, then you can do away with $N_0$.

For these non-pathological functions (extended to non-integer points), the various asymptotic notations have equivalent definitions in terms of limits:


$f = O(g)$ if $\limsup_{n\to\infty} f(n)/g(n) &lt; \infty$.
$f = \Omega(g)$ if $\liminf_{n\to\infty} f(n)/g(n) &gt; 0$.
$f = \Theta(g)$ if both these conditions hold.
$f = o(g)$ if $\lim_{n\to\infty} f(n)/g(n) = 0$.
$f = \omega(g)$ if $\lim_{n\to\infty} f(n)/g(n) = \infty$.