1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).$$

$\endgroup$
  • $\begingroup$ 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".) $\endgroup$ – Marnix Klooster Aug 5 '17 at 21:55
0
$\begingroup$

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)$

$\endgroup$
0
$\begingroup$

Your proof is correct, and here is how I would write down your proof:$% \require{begingroup} \begingroup \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} %$

$$\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 %$

$\endgroup$

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.