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.

  • 1
    $\begingroup$ 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)$. $\endgroup$ – Bernard Feb 26 '18 at 11:21
  • $\begingroup$ Roughly speaking, the ratio $\dfrac{f(x_n)}{x_n^2}$ is bounded when $n$ is large enough. $\endgroup$ – Bernard Feb 26 '18 at 11:23
  • $\begingroup$ @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. $\endgroup$ – Salamo Feb 26 '18 at 12:28
  • 1
    $\begingroup$ Because $\Bigl(\dfrac{\log n}n\Bigr)^2$ is $o\Bigl(\dfrac{\log n}n\Bigr)$. $\endgroup$ – Bernard Feb 26 '18 at 12:42
  • $\begingroup$ Ah, of course!... Thank you! $\endgroup$ – Salamo Feb 26 '18 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.