Why is the formal definition of Big O notation formulated as such?

Question

Consider the formal definition:

f(n) = O(g(n))

Why is it not:

f(n) = O(f(n))

or

f(n) = O(c*f(n))

since for the Big O analysis, f(n)=2n and g(n)=n are identical?

I am confused by the function f(n) using another function.

---

Update

Why isn' t the definition as follows:

f(n) <= c*abs(g(n))

What does the formal O(g(x)) add to the definition? It seems like it overcomplicates things.

Answer 1

This is an extremely weird definition and is actually new to me. The symbols, as defined by Bachmann and Landau, are not defined like that.

Unfortunately, the German wikipedia is the only source, I can find exactly this, as of now, but I suppose you can see without much translation, that is defined as .
(Please note: the french wikipedia has the following similar definition , which I suppose basically states the same, although I think it is incorrect, given that f(n) is something completely different than f).

As I explained in response to a different question, O means "the order of", and thus O(g) is actually the set of all functions, that have the same order as g. It makes only sense to say:

• f is the same order as g (or more explicitely: the order of f is the order of g), which is O(f) = O(g)
• f is in the order of g, which translates to f ∈ O(g)

So for the sake of nitpicking (which is the fun part in formalization), one can say the definition you criticize is indeed wrong.

Answer 2

Wikipedia has a formal definition of the big O notation. That is:

f(x) = O(g(x))

if and only if there exists a positive real number M and a real number x0 such that

|f(x)| <= M * |g(x)|  for all x > x0

Answer 3

The Big-Oh notation is used to relate two functions, f and g. Therefore, there must be two functions in the definition.

When we write

f(n)=O(g(n))

we do not define the function f (that is already known) and the = doesn't mean "equals". You may read the notation either as "f(n) is (in some sense) less-than-or-equal than g(n)" or, if you like sets, as "f(n) belongs to the set O(g(n))".

That said:

f(n) = O(f(n))
f(n) = O(n*f(n))

are both always true.

Answer 4

I am confused on defining the function f(n) using another function

Don't be confused, it's actually pretty simple. The big O notation is an inequation. That means that we can find multiple upper bounds for f(n) and still be correct, hence, although we can write f(n) = O(f(n)) and be correct it's, depending on f(n), often not what we are intending to express.

It's a measure of growth rates. f(n) = 2n does not grow faster than f(n) = n. Both growths are linear.

f(n) = O(n*f(n))

I'll assume you meant the second n to be a constant c.

By definition of Big O, this constant is already in the inequation. So when you write the usual f(n) equals Big O(g(n)) you're actually writing abs(f(n)) <= c * abs(g(n)). If you can find a constant factor you needn't mention it, because the definition of Big O, the inequation, already takes care of that and g(n) is then considered an upper bound of f(n).

Maybe the common wording can help you: f(n) = O(g(n)) means the function f does not grow faster than g, except maybe for a constant factor c.

Answer 5

See the formal definition of Big oh states f(n)=O(g(n)) means there are positive constants c and k such that 0<=f(n)<=cg(n) where n>=k.

It means value of f(n) for any n>=k is less than or equal to value of g(n) multiplied by some constant. Its covering both cases.

What we want to say by this definition is that there exists some function g(n) which is always greater than or equal to f(n) for any particular n. We know then that f(n) has some particular limit which it cannot cross which is essential need of Big Oh notation as it tells us that some particular program cannot take more time than its Big oh notation.

As jpalecek said, f(n)=O(g(n)) notation is like sets meaning f(n) belongs to set O(g(n)). There can be more functions which belong to the set O(g(n)). Thats why we require two functions for Big Oh analysis.

Answer 6

f(n) = O(f(n)) is a trivial statement. It's basically x = x and you gain no information from f(n) = O(f(n)). The whole point of Big-O notation is to compare some complicated function to a much simpler one to gain better understanding of its long term behavior.