# Landau notation (big and little)

Suppose $(x_n)_{n\in\mathbb{N}}$ is a non-negative zero sequence and $x_n<\frac{\log(n)}{n}$.

Consider a function $f(x_n)=O(x_n^2), n\to\infty$.

Am I right, that we can conlude that $$f(x_n)=O\left(\frac{\log(n)}{n}\right), n\to\infty$$ but not $$f(x_n)=o\left(\frac{\log(n)}{n}\right), n\to\infty?$$

The big-Oh result should follow since $$\lvert f(x_n)\rvert\leq M x_n^2\leq M\frac{\log(n)^2}{n^2}\leq M\frac{\log(n)}{n}$$ for some $M>0$ and $c>c*$ for some $c*$ (since $f(x_n)=O(x_n^2), n\to\infty$) and because $\left(\frac{\log(n)}{n}\right)^2\leq \frac{\log(n)}{n}$ for large $n$.

The little-oh statement is not satisfied in general, I think, because we cannot choose $M>0$ arbitrary in general because the assumption does not tell us this.

• Not which statement woth$o$ you mean, but if $x_n=O\Bigl(\dfrac{\log n}n\Bigr)$, and $f(x_n)=O(x_n^2)$, then $f(x_n)=o\Bigl(\dfrac{\log n}n\Bigr)$. – Bernard Feb 26 '18 at 11:21
• Roughly speaking, the ratio $\dfrac{f(x_n)}{x_n^2}$ is bounded when $n$ is large enough. – Bernard Feb 26 '18 at 11:23
• @Bernard I do not see why $x_n=O\left(\frac{\log n}{n}\right)$ and $f(x_n)=O(x_n^2)$ imply that $f(x_n)=o\left(\frac{\log n}{n}\right)$. For the big-Oh, i can see that but not for the little-oh. – Salamo Feb 26 '18 at 12:28
• Because $\Bigl(\dfrac{\log n}n\Bigr)^2$ is $o\Bigl(\dfrac{\log n}n\Bigr)$. – Bernard Feb 26 '18 at 12:42
• Ah, of course!... Thank you! – Salamo Feb 26 '18 at 12:43