# Understanding big O notation

I'm not a mathematician by any stretch and I'm trying to translate some maths terms into simple maths terms. Please don't laugh, I do consider this complicated!

The equations in question are

O(n) and O(n ^ 2)


I believe n ^ 2 translates to the power of, in this case it is also the equivalent of squaring it (i.e. n * n).

However, I can't get my head around O in terms of what it is describing. Wiki says it's the limiting behaviour. So, does this mean O is more of a description than a function or command? In my understanding, the following 2 equations are the same

O(n^2)

n^2

• many years ago I asked this in a math forum, they said $f(x)=O(g(x))$ iff $(\exists M>0)(\forall x>M)(|f(x)|\le M|g(x)|)$. by the way a notation like $f(x)<< g(x)$ has more to say. – user59671 May 14 '13 at 10:21
• I will never, ever, understand even a quarter of that :) – Dave May 14 '13 at 10:24
• $(\exists M>0)(\forall x>M)(|f(x)|\le M|g(x)|)$ means: "There's some $M>0$ such that for all $x>M$ we have $f(x)<Mg(x)$" (replace $x$ by $n$ ) – user59671 May 14 '13 at 10:29
• @CutieKrait Hm in such precise language, it seems strange not to consider O(g(x)) to be a class of functions, as in the second answer to this question. I feel the = should be replaced by "is element of" – Jacob Akkerboom May 14 '13 at 11:03
• Of course: $O(\cdot)$ is a set of functions. But almost nobody avoids the abuse of notation $f=O(g)$. – Siminore May 14 '13 at 11:06

Quickly, $O(n^2)$ is any function $f=f(n)$ such that $$\left| \frac{f(n)}{n^2} \right|$$ remains bounded as $n \to +\infty$. It may be $n^2$ itself, but it may also be $n$, or $\sin \cos n$, etc.
• Well, the big-O is a notation that is sometimes understood with some differences by scientists. I would rather use a different notation for $$\lim_{n \to +\infty} \frac{f(n)}{n^2}=L\neq 0.$$ However, some scientists identify the two cases. – Siminore May 14 '13 at 9:43
The formally correct $O$-notation has been explained in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=296&t=31517&start=20 . Namely, suppose we have been given a positive $g$ defined in a punctured neighborhood of $x_0$. Now $O_{x_0}(g)$ is the class of all functions $f$ such that the ratio $f/g$ is bounded in some punctured neighbourhood of $x_0$. This definition and notation is more rigorous than for example the one given in some university's computer science courses.