Can $O(\sqrt{x})$ be considered $o(x)$?

Question

This example challenges my understanding of $O(x)$ and $o(x)$ notation. One the one hand I have:

$$ A = B + o(x)$$

Another part of the paper uses big-O instead of little-o and says:

$$ C = D + O(\sqrt{x}) \stackrel{?}{=} D + o(x)$$

I am willing to take a huge sacrifice on the error term for simplicity, but I am struggling to see if this is correct. In particular, is it the case that: $\bbox[2px, border:2px solid #55FF88]{ \tfrac{1}{x}(C-D) \asymp 0 }$ or $\bbox[2px, border:2px solid #5588FF]{\tfrac{1}{x}(C-D) \sim 0}$ ?

Which limit for $x$ are you considering? $x\to 0$, $x\to \infty$, etc? — user251257, Jul 25 '15 at 13:21
@user251257 Oh my. What an important question. I guess $\boxed{x \to \infty}$, but $x \to 0$ could be important. — cactus314, Jul 25 '15 at 13:25
for $x\to\infty$ it is true. for $x\to 0$ it is the other way around. please edit your question to make it unambiguous. — user251257, Jul 25 '15 at 13:35

score 1 · Accepted Answer · answered Jul 25 '15 at 13:05

1

Yes. If we have $f(x) \in O(\sqrt{x})$, then $f(x) < k\sqrt{x}$ for some $k$ and all $x$ sufficiently large.

Then we have $f(x) < \frac{k}{\sqrt{x}}x$, but since $\frac{k}{\sqrt{x}}$ gets abritarily small, we can conclude that $f(x) < cx$ or all $c$ and all $x$ sufficiently large. This is equivalent to $f(x) \in o(x)$.

We can make much stronger claims. For example $f(x) \in o(\sqrt{x}\ln(x))$ would be true too.

answered Jul 25 '15 at 13:05

wythagoras

25,026

@Bernard Yes. Note I wrote for all $c$. – wythagoras Jul 25 '15 at 13:13

score 0 · Answer 2 · answered Jul 25 '15 at 13:28

Yes: if $f(x)=O(\sqrt x)$ there exists a constant $K>0$ such that $\lvert f(x)\rvert\le Kx$ for large $x$. This implies $$0\le\biggl\lvert\frac{f(x)}x\biggr\rvert\le\biggl\lvert\frac{K}{\sqrt x}\biggr\rvert $$ which tends to $0$ as $x$ tends to $+\infty$.

For the second point, if $C-D=o(x)$, then $\;\dfrac{C-D}x=o(1)$ so $\lim_{x\to\infty}(C-D)=0$. But we can't say a function is equivalent to $0$; equivalence of functions makes sense only for non-identically $0$ functions.

Can $O(\sqrt{x})$ be considered $o(x)$?

2 Answers2