Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to take the limit $x\to 0$ and prove or disprove the following statements concerning Landau notation.

(a) $O(x^{3/2})\subset o(x)\subset O(x^{1/2})$

(b) $(1+O(x))^2=1+O(x^2)$

I know the deifiniton of the O-notation and also what it means but i have no idea how to show these kinds of inequalities.

I would appreciate it if somebody can help me.

share|improve this question
1  
Different authors define what $f(x)=O(g(x))\text{ and }f(x)=o(g(x))$ mean in different (though equivalent) ways. What definitions are you using? The reason I ask is that the answers would be different depending on the definitions you'd like to use. –  Rick Decker Oct 18 '12 at 23:39
1  
Give us the definitions please and we'll help you. –  nikita2 Oct 19 '12 at 0:18
    
I use the definition from wikipedia: $f(x)=O(g(x)) as x-> 0$, if and only if there exist positive numbers $M$ and $\delta$ such that $|f(x)|\le M*|g(x)|$ for $|x-a|<\delta$ –  Montaigne Oct 19 '12 at 15:10

1 Answer 1

up vote 1 down vote accepted

The expressions "$f(x)=O(x)$" or "$f(x) = o(x)$" in Landau notation really mean that the function $f$ belongs to a class of functions, so strictly speaking it would be more correct to write $f \in O(x)$ and $f\in o(x)$. However, the traditional notation is the standard, so we all have to live with it. Proving these, you have to remember that you are proving set inclusions or equalities, so you have to proceed like for those.

(a) If $f(x) = O(x^{3/2})$, then $|f(x)| \le M|x|^{3/2} = (M|x|^{1/2}) |x|$ near $0$, and since $M|x|^{1/2} \to 0$ as $x\to 0$, this shows $f \in o(x)$. If you want to show strict inclusion, see that $x^{4/3} = o(x)$, but $x^{4/3} \neq O(x^{3/2})$.

Now if $f(x) = o(x)$, then $|f(x)| \le \epsilon(x) |x| = (\epsilon(x) |x|^{1/2}) |x|^{1/2}$ with $\lim\limits_{\epsilon \to 0} \epsilon(x) = 0$, so $\lim\limits_{\epsilon\to 0} \epsilon(x) |x|^{1/2} = 0$, implying that $f(x) = o(x^{1/2})$. Since $o(x^{1/2}) \subset O(x^{1/2})$ (every convergent function is locally bounded), this implies that $f(x) \in O(x^{1/2})$. Again for the strict inclusion pick a function $x^{\alpha}$ with $1/2 < \alpha < 1$.

(b) This is not true, as you can see from the simple example $f(x) = (1+x)^2 = 1+2x+x^2$. (Always test these first, i.e., just replace the $O(g(x))$ by $g(x)$ and see if the statement is true.) Obviously $(1+x)^2 = (1+O(x))^2$, but if we had $f(x) = 1+O(x^2)$, then $f(x)-1 = O(x^2)$, so $\frac{(1+x)^2 - 1}{x^2} = \frac{x+x^2}{x^2} = \frac{1}{x}+1$ would have to be bounded in a neighborhood of $0$, which it is not.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.