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)

Now, I have read up on Wiki about this but it has been written (IMO) for people who already understand it!

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


  • $\begingroup$ 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. $\endgroup$ – user59671 May 14 '13 at 10:21
  • 4
    $\begingroup$ I will never, ever, understand even a quarter of that :) $\endgroup$ – Dave May 14 '13 at 10:24
  • $\begingroup$ $(\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$ ) $\endgroup$ – user59671 May 14 '13 at 10:29
  • $\begingroup$ @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" $\endgroup$ – Jacob Akkerboom May 14 '13 at 11:03
  • $\begingroup$ Of course: $O(\cdot)$ is a set of functions. But almost nobody avoids the abuse of notation $f=O(g)$. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ This is much easier for me to understand, thank you for taking the time. Is O also "order of" ? $\endgroup$ – Dave May 14 '13 at 9:41
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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