Discrete Mathematics: Prove that f(x) is in O(x)

Question

Prove that $$\frac{2x^{2}+x}{x+1}$$ is in $O(x)$

My naive way is just to say that $f(x) = O(x^2)/O(x) = O(x)$ but that is probably too fast — Mathias711, Apr 17 '14 at 08:19

score 1 · Answer 1 · answered Apr 17 '14 at 08:20

1

$\frac{2 x^2 +x}{x+1} <\frac{2x^2 +x^2}{x}=3x=O(x)$.

answered Apr 17 '14 at 08:20

Alex

19,262

Can you please show more of your work. – M.E. Apr 17 '14 at 08:21
$\frac{1}{x+1}<\frac{1}{x}, x< x^2$ for $x >1$ – Alex Apr 17 '14 at 08:22
In the sense of large $x$, the inequality follows. Now $M = 3$ is your constant. – IAmNoOne Apr 17 '14 at 08:24
Sorry,the prove must use the definition of O(x). – M.E. Apr 17 '14 at 08:58
Take the limit of your function and $3x$ as $x \to \infty$. What do you get? – Alex Apr 17 '14 at 09:09

score 0 · Accepted Answer · answered Apr 17 '14 at 10:03

0

By definition, we have that

$$\frac{2x^2+x}{x+1}=\mathcal O(x)\iff \exists\,\text{a constant}\;M\;\;s.t.\;\;\left|\frac{\frac{2x^2+x}{x+1}}x\right|=\left|\frac{2x+1}{x+1}\right|\le M$$

But we know that

$$\lim_{x\to\pm\infty}\frac{2x+1}{x+1}=2\;,\;\;\;\text{ so}\ldots$$

answered Apr 17 '14 at 10:03

DonAntonio

211,718
17
136
287

Great Answer. Thank you sir. – M.E. Apr 18 '14 at 06:14

Discrete Mathematics: Prove that f(x) is in O(x)

2 Answers2