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

Please could someone review my proof of the following big-O estimate thanks


f(n) is O(g(n)) if there are positive constants C and k such that:

(1)f(n) $\le Cg(n)$ whenever n>k

(2)f(n) is O(g(n)) $\equiv \space \exists C \exists k \forall n(n>k \rightarrow f(n) \le Cg(n))$

To prove big-O, we will choose values for C and k and prove n>k implies f(n) $\le$Cg(n)

First, show $f_1(n)=n^2+8 = O(n^2)$

Choose k=1. Assuming n>1, then

$ \frac {f_1(n)}{g_1(n)} =\frac {n^2 + 8}{n^2}< \frac{n^2 + 8n^2}{n^2}=9$

Choose c = 9. Note that $ 8< 8n^2$. Thus, $n^2+8$ is $O(n^2)$ because

$n^2 +8 \le 9n^2$ whenever n>1.

Second, show $f_2(n)=n + 1 = O(n)$

Choose k=1. Assuming n>1, then

$ \frac {f_2(n)}{g_2(n)} =\frac {n+1}{n}< \frac{n+n}{n}=2$

Choose c = 2. Note that $ 1< n$. Thus, $n+1$ is $O(n)$ because

$n+1 \le 2n$ whenever n>1

Using theorem: Suppose that $f_1(n)\space is\space O(g_1(n))\space and \space f_2(n) \space is \space O (g_2(n)). Then (f_1f_2)(n) \space is \space O(g_1(n)g_2(n)) $

$\therefore (n^2+8)(n+1) \space = O(n^3) $

share|cite|improve this question
You use $k$s and $c$s without explaining what they are. Also, neither of the relationships here can hold: $\frac {n^2 + 8}{n^2}< \frac{n^2 + 8}{n^2}=9$. It might be a little easier to just expand $(n^2+8)(n+1)= n^3+n^2+8n+8$, and find a bound for that. – copper.hat Dec 16 '12 at 16:31
ok thanks. typo amended above regarding you 2nd point – bosra Dec 16 '12 at 16:39
Hi, it looks good, but you still have the extraneous $k$s and $c$s around. – copper.hat Dec 16 '12 at 16:46

Your Answer


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

Browse other questions tagged or ask your own question.