Limit proof as x approaches infinity

[fishturtle1]

Homework Statement

Verify the following assertions:
a) $x^2 + \sqrt{x} = O(x^2)$

2. Homework Equations
If the limit as x approaches $\infty$ of $\frac {f(x)}{g(x)}$ exists (and is finite), then $f(x) = O(g(x))$.

The Attempt at a Solution

Let $\epsilon > 0$. We solve for $\delta$ such that $x > \delta$ implies $|\frac{f(x)}{g(x)} - 1| < \epsilon$. Consider $|\frac {x^2 + \sqrt{x}}{x^2} - 1| < \epsilon$. Then $\frac {x^2 + \sqrt{x}}{x^2} - 1 < \epsilon$, so $\frac {x^2 + \sqrt{x}}{x^2} < \epsilon + 1$. Taking the inverse of both sides and then taking the square root of both sides, we get $\frac x{\sqrt{\sqrt{x} + x^2}} > \frac 1{\sqrt{\epsilon + 1}}$..I'm trying to get to an expression "x > some expression in terms of $\epsilon$" and then substitute that for $\delta$.

 

[mfb]

Why would you take the inverse square root of both sides?
$$\frac {x^2 + \sqrt{x}}{x^2} < \epsilon + 1$$That is good. Now simplify it.

 

[fishturtle1]

Why would you take the inverse square root of both sides?
$$\frac {x^2 + \sqrt{x}}{x^2} < \epsilon + 1$$That is good. Now simplify it.

Thanks for the response,

$\frac {x^2 + \sqrt{x}}{x^2} = 1 + \frac{\sqrt{x}}{{x^2}} = 1 + \frac 1{x^{3/2}} < \epsilon + 1$ so, $\frac 1{x^{3/2}} < \epsilon$
Raising both sides to $-5/2$, we get $x > \epsilon^{\frac{-5}{2}} = \delta$. Thus, we can conclude the limit as x approaches $\infty$ for $\frac {x^2 + \sqrt{x}}{x^2} = 1$. Thus, ${x^2 + \sqrt{x}} = O(x^2)$.

 

[Ray Vickson]

Homework Statement

Verify the following assertions:
a) $x^2 + \sqrt{x} = O(x^2)$

2. Homework Equations
If the limit as x approaches $\infty$ of $\frac {f(x)}{g(x)}$ exists (and is finite), then $f(x) = O(g(x))$.

The Attempt at a Solution

Let $\epsilon > 0$. We solve for $\delta$ such that $x > \delta$ implies $|\frac{f(x)}{g(x)} - 1| < \epsilon$. Consider $|\frac {x^2 + \sqrt{x}}{x^2} - 1| < \epsilon$. Then $\frac {x^2 + \sqrt{x}}{x^2} - 1 < \epsilon$, so $\frac {x^2 + \sqrt{x}}{x^2} < \epsilon + 1$. Taking the inverse of both sides and then taking the square root of both sides, we get $\frac x{\sqrt{\sqrt{x} + x^2}} > \frac 1{\sqrt{\epsilon + 1}}$..I'm trying to get to an expression "x > some expression in terms of $\epsilon$" and then substitute that for $\delta$.

You have
$$\frac{x^2+\sqrt{x}}{x^2} = 1 + \frac{1}{x^{3/2}} \leq 2$$
for $x \geq 1$. Thus, $x^2 + \sqrt{x} \leq k x^2$ where $k = 2$. If you further restrict the range of $x > 0$ you can make $k$ smaller, but that is not relevant to the definition of $O(x^2)$, which just need some finite $k > 0$.

BTW: your definition of $O$ is different from those I have seen; the ones I know of do not require that $f(x)/g(x)$ have a finite limit as $x \to \infty$, they just require that there exists some finite $k > 0$ such that $|f(x)/g(x)| \leq k$ as $x \to \infty$.

 

[fishturtle1]

You have
$$\frac{x^2+\sqrt{x}}{x^2} = 1 + \frac{1}{x^{3/2}} \leq 2$$
for $x \geq 1$. Thus, $x^2 + \sqrt{x} \leq k x^2$ where $k = 2$. If you further restrict the range of $x > 0$ you can make $k$ smaller, but that is not relevant to the definition of $O(x^2)$, which just need some finite $k > 0$.

BTW: your definition of $O$ is different from those I have seen; the ones I know of do not require that $f(x)/g(x)$ have a finite limit as $x \to \infty$, they just require that there exists some finite $k > 0$ such that $|f(x)/g(x)| \leq k$ as $x \to \infty$.

Thanks for the clarification, I didn't know about the actual definition of $O$.

I should add that the textbook says this method can *sometimes* be used to prove that $f(x) = O(g(x))$. So I guess the book's method only works for certain situations.. and even if it fails, it doesn't rule out whether or not $f(x) = O(g(x))$.

 

[mfb]

You showed more than just O(x²), but showing that the limit is 1 shows the existence of the limit, of course.