# Big O Notation Explained [duplicate]

Our teacher gave us the following definition of Big O notation:

O(f(n)): A function g(n) is in O(f(n)) (“big O of f(n)”) if there exist constants c > 0 and N such that |g(n)| ≤ c |f(n)| for all n > N. I'm trying to tease apart the various components of this definition. First of all, I'm confused by what it means for g(n) to be in O(f(n)). What does in mean?

Next, I'm confused by the overall second portion of the statement. Why does saying that the absolute value of g(n) less than or equal f(n) for all n > N mean anything about Big O Notation?

My general intuition for what Big O Notation means is that it is a way to describe the runtime of an algorithm. For example, if bubble sort runs in O(n^2) in the worst case, this means that it takes the time of n^2 operations (in this case comparisons) to complete the algorithm. I don't see how this intuition follows from the above definition.

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Oct 28 '14 at 5:44
• It doesn't, because it's wrong. See also our reference questions. – Raphael Oct 28 '14 at 7:37
• I'm closing this as a duplicate because I think that the existing question sufficiently addresses your misconception. As a general rule, explaining definitions on this level is not something that SE is good at. You seem to have problems at parsing quite basic mathematical formula, and you seem to be mistaking your (instructor's?) intuition for a definition the formal one has to agree with. Therefore, this is a problem you should approach your teacher(s) with. – Raphael Oct 28 '14 at 7:39