Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

6 Answers 6

up vote 6 down vote accepted

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 O(n) is defined as lim sup of the ratio of f and g smaller than infinity.
(Please note: the french wikipedia has the following similar definition french 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.

share|improve this answer
    
+1.Interesting, but I have a minor objection (I also reviewed your answer in the link).If the O stands for Order of or Ordnung von then why there is the understanding that it is the Greek letter Omicron? Am I wrong to think that everyone thinks that the asymptotic symbols are from Greek letters e.g. Theta? –  user10326 Oct 2 '11 at 14:05
    
@user10326: It is indeed from the Greek letter Omicron (as I the answer I linked states), but also Omega and Theta, because in fact, there's 5 Landau symbols. So for one, O itself wouldn't have quite cut it. But also, we have a thing for Greek letters in Germany. The symbol for Ohm is in fact Omega. –  back2dos Oct 2 '11 at 14:40
    
@bacj2dos:This is my point.If it is the Greek letter O then it can not mean Order of or Ordnung von.So I am not sure how this notation fits here –  user10326 Oct 2 '11 at 15:26
    
@user10326: You are making two points: 1. what we now call "big O" is actually a capital Omicron. 2. Therefore it cannot mean "order of". The first is true, as the source I gave shows. The second is not, as the source I gave shows. As the Ohm-example didn't seem to impress you, I would point out, that mathematicians around the world use Sigma to represent a sum, and Pi for products, although both words come from Latin and not Greek. –  back2dos Oct 2 '11 at 16:45
    
@bac2dos:From the Ohm-example I got that the Omega is a convention.So it seems that in the asymptotic notation, somehow by coincidence the word Order matches the O of the notation? –  user10326 Oct 2 '11 at 17:30

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.

share|improve this answer
    
f(n) belongs to the set O(g(n)).So shouldn't it be defined what does the set include? –  user10326 Oct 2 '11 at 10:17

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.

share|improve this answer
    
If it is an inequation why does the definition use an = sign?Also why didn't they just use c * abs(g(x)) to be more clear and introduced the notation of O(g(x)) ?I can't see what the new notation of O offers –  user10326 Oct 2 '11 at 10:05
    
Why not f(n)<=c * abs(g(x)) and stop there? What does the formal O(g(x)) offer? –  user10326 Oct 2 '11 at 10:08
    
@user10326: Tough questions. I'd argue that the big O notation describes a set of functions and the equals sign should mean "the function is an element of" or "f statisfies the criteria of the big O and is thus part of it". The notation itself is just a convenient way to describe the rather long criterias. See this picture here: linux-related.de/coding/pics/o-not.gif –  Falcon Oct 2 '11 at 10:10

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
share|improve this answer
    
Concise and to the point. –  Job Oct 2 '11 at 13:22

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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