Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Big O Notation is formally defined as:

Let $f(n)$ and $g(n)$ be function from positive integers to positive reals. We say $f = \theta(g)$ (which means that "$f$ grows no faster than $g$*) if there is a constant $c>0$ such that $f(n) ≤ c ⋅ g(n)$.

Using this definition how is:

  • $n^2 + n$ simplified to $n^2$
  • $n + 20$ simplified to $n$

I don't see a $c$ constant that defines their relationship. How do the above examples work?

share|cite|improve this question
up vote 2 down vote accepted

Try to prove that if $n$ is a positive integer then $n^2+n\le2n^2$ and $n+20\le21n$.

share|cite|improve this answer
Thanks you again! – user26649 Jun 17 '12 at 1:54

More specifically, $|f(n)| \le c |g(n)|$ for $n$ sufficiently large. So $$|n + 20|\le 2n$$ if $n\ge 20$.

share|cite|improve this answer
In this case we usually say, "as $n\to\infty$." – ncmathsadist Jun 17 '12 at 1:38
The definition the way OP has given it leaves no room for "sufficiently large". – Gerry Myerson Jun 17 '12 at 1:38
If you want for $n\ge 1$, use the last commenter's definition. If $n=0$, your goose is cooked. – ncmathsadist Jun 17 '12 at 1:39
The finding by the last commenter works if $n \ge 1$ is required. If you want $n\ge 0$, your goose is cooked. – ncmathsadist Jun 17 '12 at 1:40

Your Answer


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