Landau notation (big and little)

36 Views Asked by At

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.