1
$\begingroup$

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)$?

$\endgroup$
  • 1
    $\begingroup$ The constants are there precisely so you can disregard constant factors. They ensure that, as an example, $f(n)=O(g(n))$ iff $Cf(n)=O(g(n))$. $\endgroup$ – Yuval Filmus Jul 7 '18 at 11:11
  • 1
    $\begingroup$ It seems that your real difficulty is with formal definitions. I suggest reviewing (or studying) "intro to proofs" or formal logic. $\endgroup$ – Yuval Filmus Jul 7 '18 at 11:12
  • $\begingroup$ @YuvalFilmus can you explain more why constants can disregard constant factors? $\endgroup$ – John Sall Jul 7 '18 at 11:34
  • $\begingroup$ @YuvalFilmus I don't think my problem with formal definition, maybe I have a problem with them, but my priority is understanding the concept of those constants and the asymptotic notations. I don't understand the concept behind them. I mean, if f(n) = n^2 + 1 and g(n) = n^3, then obviously n^3 is bigger than n^2 as n gets larger. why are we even proving that? it doesn't make any sense. and why are we putting this symbol O here : O(g(n)). $\endgroup$ – John Sall Jul 7 '18 at 11:59
  • $\begingroup$ In mathematics, nothing is obvious. We have to prove everything. $\endgroup$ – Yuval Filmus Jul 7 '18 at 12:07
2
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ I really appreciate your effort for trying to explain, and you took the time to write all this. But I think I got more confused now. $\endgroup$ – John Sall Jul 7 '18 at 12:57
  • $\begingroup$ I suggest contacting a TA. Stackexchange isn't the best forum for discussions. $\endgroup$ – Yuval Filmus Jul 7 '18 at 12:58
  • $\begingroup$ What is s TA stand for? $\endgroup$ – John Sall Jul 7 '18 at 12:59
  • $\begingroup$ Teaching assistant. $\endgroup$ – Yuval Filmus Jul 7 '18 at 12:59
  • $\begingroup$ You mean in my college? We don't have one, only the lecture instructor is there, and he's taking the lab too, I don't know if he can help. $\endgroup$ – John Sall Jul 7 '18 at 13:00
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.