# Proving Big-O notation

I need to prove, that $5n^2+7=O(2^n)$

I came up with the following proof, is this correct?

To prove this, we need to show $5n^2+7 \le c*2^n$ for $n \ge b$

We know, that $7\le n^2$ for ever $n\ge3$ (Can we just assume this or do we have to prove it?)

Thus, we get $5n^2 + n^2 < c*2^n$ After minimizing the left side, we get $6n^2 \le c*2^n$

We know, that $n^2 \le 2^n$ for every $n \ge 4$ Thus, we get $6*2^n \le c*2^n$ for every $n\ge4$

So we can conclude, that our b is 4 and our c is 6.

Is this proof correct?

Your proof is correct, try to keep it as concise as possible though.
Choose $n_0 = 5$, $c = 6$, then $$5n^2 + 7 < 5n^2 + n^2 = 6n^2 < 6 \cdot 2^n,$$ so $$5n^2 + 7 \in \mathcal{O}(2^n).$$

• Note that I don't like this shortening of the OP's proof, for two reasons. First, the constant $\;c=6\;$ is now magically pulled like a rabbit out of a hat at the start of the proof. (See also the introduction to EWD1300.) Second, the key facts that are used here (namely, that $\;7 < n^2\;$ and $\;n^2 < 2^n\;$ for large enough $\;n\;$) are absent, which puts more burden on the reader to try and reconstruct/guess what the proof author was doing. (Again, see EWD1300, under "The role of the hints".) – MarnixKlooster ReinstateMonica Aug 5 '17 at 21:55

Another way to prove this is:

We know that $$\lim_{n \rightarrow \infty} \frac{5n^2}{2^n}=0$$

Thus for $\epsilon=1,\exists n_1 \in \mathbb{N}$ such that: $$5n^2 <2^n, \forall n \geqslant n_1$$ where $C_1>0$.

Also we have that $$\lim_{n \rightarrow \infty} \frac{7}{2^n}=0$$

Thus for $\epsilon =1,\exists n_2 \in \mathbb{N}$ such that: $$7 < 2^n,\forall n_ \geqslant n_2$$

Thus for $n_0=\max\{n_1,n_2\}$ we have that $5n^2+7=O(2^n)+O(2^n)=O(2^n)$


$$\calc 5n^2 + 7 = O(n^2) \op=\hint{definition of \;\cdot = O(\cdot)\;} \langle \exists c : c>0 : \langle \forall_{l.e.} n :: 5n^2 + 7 \le c2^n \rangle \rangle \op\when\hint{\;7 \le n^2\; for \;n \ge 3\;} \langle \exists c : c>0 : \langle \forall_{l.e.} n :: 6n^2 \le c2^n \rangle \rangle \op\when\hint{\;n^2 \le 2^n\; for \;n \ge 4\;} \langle \exists c : c>0 : \langle \forall_{l.e.} n :: 6 \times 2^n \le c2^n \rangle \rangle \op\when\hint{choose \;c := 6\;} \true \endcalc$$

This uses the abbreviation 'for all large enough $\;n\;$': $$\langle \forall_{l.e.} n :: P(n) \rangle \;\equiv\; \langle \exists b :: \langle \forall n : n \ge b : P(n) \rangle \rangle$$ which (at least for me) make many proofs around complexity and big-$O$ easier to find and understand.

Whether or not you want to go further, and also prove that $\;7 \le n^2\;$ for $\;n \ge 3\;$, and that $\;n^2 \le 2^n\;$ for $\;n \ge 4\;$, depends on the context and what you are allowed to assume for your exercise/homework/assignment.

$% \endgroup %$