Big O Notation - what does the natural number M and constant factor C mean?

Question

I understand what is Big O Notation when it comes to identifying the complexity or worst case based on a code excerpt.

In class, I was taught that when it comes to complexity and Big O Notation, we ignore small arguments n that are below M and constant factors C.

This was given to me in class:

In Big-Oh notation. Let f be a function from N to the positive reals. (Think of f(n) as the running time for an argument of size n. It could be worst case or it could be average case.) Let g be another such function. We say that f ∈ O(g) when there is some natural number M and constant factor C, such that for all n > M, we have f(n) <= C × g(n). In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)

May I know what does this statement mean, specifically:

1. Why do we say :

Let f be a function from N to the positive reals.

2. Why does it mean by:

Let g be another such function.

3. What does it mean by:

We say that f ∈ O(g) when there is some natural number M and constant factor C, such that for all n > M, we have f(n) <= C × g(n). In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)

4. How does these above excerpt relate to ignoring small arguments and constant factors C?

Answer 1

To summarize: C times g eventually dominates f.

1 & 2.

Let f be a function from N to the positive reals. (Think of f(n) as the running time for an argument of size n. It could be worst case or it could be average case.) Let g be another such function.

OK: f and g are functions from the natural numbers (N) to the positive reals. Why from natural numbers? We are assuming the size of the argument is something we can precisely specify. A natural number is something we can precisely specify. A real number is not. Why to the positive reals? We are assuming the running time is not necessarily something we can precisely specify.

But what's important here is actually not what is being said but what is being not said. Nobody said f is a monotonically increasing, or that g is a polynomial, or whatever. All we know is that f and g are functions. That is almost all there is to it. Yes, they map from naturals to positive reals, but this is a pretty small restriction as far as restrictions go. So the point here is: there are many, many functions f and g to choose from. The only somewhat important restriction is that there are many more reals than naturals.

3.

We say that f ∈ O(g) when there is some natural number M and constant factor C, such that for all n > M, we have f(n) <= C × g(n). In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)

M and C are constants. We choose M and C, and we are done. The important point here is that there is at least one M and at least one C that satisfies the sentence. Not: any M nor any C. The statement is that there is at least one such M and C.

n, on the other hand, is not a constant. We can choose n to be any number so long as it is bigger than M. The statement says that for any choice of n (bigger than M), at least one value of C can be found, so that if you multiply g(n) by C, this product will be bigger than f(n). It doesn't matter what n is, as long as it's bigger than M.

The reason we consider the constants M and C becomes clear when we suppose one of the restrictions were lifted. Suppose the statement said nothing about M:

We say that f ∈ O'(g) when there is some constant factor C, such that for all n, we have f(n) <= C × g(n). In logical symbols: ∃C. ∀n f(n) <= C × g(n)

Now this says: consider the space of all possible outputs of f and all possible outputs of g. If we "dilate" the space of outputs of g by a constant C, every one of them will be bigger than any one of the points in f. Now this is a stronger statement than when we specified M. What if f(0) = 10 and g(0) = 0? Now, there can be no C that makes Cg(0) > Cf(0). So, M "cuts off" these bad edges.

This page has a great explanation and visual, as well: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

Answer 2

For (1) and (2): Generally, within a proof or within a definition, the text Let x be a Y is a part of a demonstration that all x which satisfy the condition Y have an additional property Z. A proof will demonstrate that the conclusion Z is true for X. Then, because no condition was specified on X other than Y, one concludes that for all X which have the condition Y the condition Z is also true.

You'll have to work through (3) yourself. There is no substitute except to break that statement into smaller pieces, make an understanding of each of the pieces, then put them together into an understanding of the entire statement.

For (4): The constant C appears in the statement itself, and it is particularly important that the C appears with an existential qualifier:

∃C. ∀n > M. f(n) <= C × g(n)

That gives C meaning within the statement. To express the meaning we do better to look at the entire statement:

∃M. ∃C. ∀n > M. f(n) <= C × g(n)

At the center of this statement we want to express the idea that g is "bigger" than f. Except, we are concerned with the eventual behavior of f and g, not their behavior for small values. Hence, the addition of ∃M to the statement. That is saying that eventually g is bigger than f. And, we are more interested in the "shape" of f and g, which gives us the constant C.

An instructive exercise is to rewrite the statement with double negatives:

~ ~ ∃M. ∃C. ∀n > M. f(n) <= C × g(n)

Then push the second negation through the statement:

~ ∀M. ∀C. ∃n > M. f(n) > C × g(n)

Then consider what the statement within the first negation means.