What is the constant $C$ in the definition of asymptotic notations?

Question

For example in the definition of $\Theta$:

$f(n) = \Theta(g(n)$ if there exist positive constants $c_1, c_2$ and $n_0$ such that $$ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for all } n \geq n_0. $$

I was scratching my head for two weeks since we took this definition in class. Why do we need this constant anyways? Shouldn't we get rid of all constants because they aren't significant?

Why can't we just say $g(n) \leq f(n) \leq g(n)$?

Answer 1

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>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>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) < \infty$.
• $f = \Omega(g)$ if $\liminf_{n\to\infty} f(n)/g(n) > 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$.

Answer 2

Why can't we just say $g(n)\leq f(n)\leq g(n)$?

Because the only way that we can have $a\leq b\leq a$ is if $a=b$.

Answer 3

I will strongly rely on the intuition here. Consider two excerpts of codes in C language, that does the same thing.

Excerpt 1:

if (a>b) {
    result = x;
} else {
    result = y;
}

Excerpt 2:

result = a > b ? x : y;

Suppose that both excerpts are inside a $n^2$ loop. So, Excerpt 1 runs $4n^2$ instructions, while Excerpt 2 runs $n^2$ instructions. We have a difference of constant $c=4$ between the two cases (even though both excerpts do the same thing).

But the difference between $4n^2$ and $n^2$ is realistic? To answer this, we have to know:

(1) both excerpts are translated into different machine instructions? we need to know all the details of the compiler used.

(2) what area the specific machine (processor) that we are compiling this?

(3) what if we change the language, for example, from C to Java? The algorithm will have the same performance? Again, we need to know the how to answer (1) and (2).

So, if algorithm analysis were to pay attention to all these technological details, it would be practically impossible or too tricky to come up with useful conclusions. That's the main reason to use the constant in assymptotic notation. It hides details like programming languages, compiler, processor, ... But it still allows to compare different ideas on designing algorithms.