1

Let's consider classic big O notation definition (proof link):

The $O(f(n))$ is the set of all functions such that there exist positive constants $C$ and $n_0$ with $$|g(n)| ≤ C * f(n)$$ for all $n ≥ n_0$

According to this definition it is legal to do the following:

$$g(n) = 9999 * N^2 + N = O(9999*N^2)$$

And it is also legal to note function as:

$$g(n) = 9999 * N^2 + N = O(N^2)$$

As you can see the first variant $O(9999*N^2)$ is much more precise than the second one.

The question is: why nobody use the first variant?

No Name QA
  • 163
  • 3
    Perhaps "precise" is not the way to distinguish the two statements. By the definition the function classes $O(9999*N^2)$ and $O(N^2)$ are equal, so the choice between them is likely based on brevity. However one could give a more "precise" (narrower) description of $g(N)$ using a "residual" term or a little-oh notation. Would an Answer along those lines be of interest to you? – hardmath Oct 23 '18 at 14:32
  • @hardmath Thank you! This part However one could give a more "precise" (narrower) description of g(N) using a "residual" term or a little-oh notation is the most interesting for me. Could give more detailed explanation about it? – No Name QA Oct 23 '18 at 14:37
  • @hardmath Could you also provide definition of that is function classes please? – No Name QA Oct 23 '18 at 14:57

1 Answers1

1

The definition of $g(n) \in O(f(n))$ tells us this is a class (set) of functions. So $O(n^2) = O(9999n^2)$ because these are equal as sets (any function belonging to the left side belongs to the right side, and conversely).

To give a more "precise" (narrower) description requires a different sort of notation. Where an author finds it important or useful to identify the "leading term" of a function (the term whose magnitude dominates as $n\to \infty$), that can be expressed by writing a sum of the leading term plus a "residual" component.

For example, your function $g(n) = 9999n^2 + n$ belongs to $O(n^2)$, but it also belongs to a strictly smaller set of functions:

$$ g(n) = 9999n^2 + n \in 9999n^2 + O(n) $$

Here the set on the right hand side is defined by adding the specific function $9999n^2$ to each element of the function class $O(n)$. Of course one of these results is your $g(n)$.

A less precise result (but still narrower than just $O(n^2)$) would be to assert:

$$ g(n) = 9999n^2 + o(n^2) $$

This invokes the function class $o(n^2)$, defined more generally by:

$$ g(n) \in o(f(n))\; \text{ if and only if } \;\lim_{n\to \infty} \frac{g(n)}{f(n)} = 0 $$

Intuitively $o(n^2)$ means those functions which become arbitrarily small in ratio to $n^2$ (as $n$ grows arbitrarily large).

To summarize, your function $g(n)$ can be described more precisely by pulling out the leading term $9999n^2$ and estimating the growth of what remains (the residual term), namely:

$$ g(n) - 9999n^2 = n \in O(n) \subset o(n^2) $$

hardmath
  • 37,015