Timeline for Big O and little o notation explained?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 15, 2017 at 20:34 | comment | added | whuber♦ | (+1) Thank you for the reference. E.L. Lehmann is well respected, so the sloppiness in that definition is a surprise. The Wikipedia article is much more general, rigorous, and correct. I would speculate that Lehmann doesn't feel a need for full generality because he will only be using simple and eventually monotonic nonzero sequences like $n$, $1/n$, $1/n^p$, etc., for his $x_n$, for which these problems don't arise. In the preface he makes it clear that this is an "elementary" volume and is not proof-oriented. | |
| May 15, 2017 at 20:20 | comment | added | Taylor | @whuber I am using definition 1.4.1 on page 18 of amazon.com/Elements-Large-Sample-Theory-Springer-Statistics/dp/… | |
| May 15, 2017 at 20:11 | comment | added | whuber♦ | In my first comment I explained why your little-o definition must be incorrect. For instance, with $a_n=(1+(-1)^n)/n$ and $x_n=1+(-1)^n$ we do have $a_n$ is $o(x_n)$, but $a_n/x_n$ does not have a limit (because the ratio is undefined for infinitely many $n$). You really do need to use standard definitions rather than hoping intuitive shortcuts will work. | |
| May 15, 2017 at 19:30 | comment | added | Taylor | @whuber the little-o definition is fine, but I agree that the examples were lacking. I added yours in there. | |
| May 15, 2017 at 19:29 | history | edited | Taylor | CC BY-SA 3.0 |
added 270 characters in body
|
| May 15, 2017 at 17:35 | comment | added | whuber♦ | Thank you for working to fix that up. Note that your little-o definition still needs to be corrected. I would also suggest not oversimplifying, because that might cause more confusion: when $a_n$ is $o(1/n)$ it is rarely the case that $a_n=c/n^p$ for any $p \gt 1$. As examples, consider that $1/(n\log(n))$ and $1/n^2 + 1/n^3$ are both $o(n)$ but neither is of the form $c/n^p$. The little-o and big-O notations are only referring to asymptotic behavior, not to specific formulas for all $a_n$. | |
| May 15, 2017 at 16:40 | history | edited | Taylor | CC BY-SA 3.0 |
added 20 characters in body
|
| May 15, 2017 at 13:40 | comment | added | whuber♦ | Although the intuitions you share are sort of on target, much of this answer is wrong. Please take some care with the subtleties. For the little-o notation, note that the limit in your definition might not exist. (Consider $x_n=1+(-1)^n$, which causes you to divide by zero infinitely often.) For the big-O notation, note that when $a_n = O(1/n)$ it is not necessarily the case that $na_n$ approaches a limit or even, if it does, that the limit be positive. A simple counterexample is the true statement that $a_n=n^{-2}$ is $O(1/n)$. Another counterexample is that $a_n=-1/n$ is $O(1/n)$. | |
| May 15, 2017 at 4:08 | history | edited | Taylor | CC BY-SA 3.0 |
deleted 479 characters in body
|
| May 15, 2017 at 4:02 | history | edited | Taylor | CC BY-SA 3.0 |
added 92 characters in body
|
| May 15, 2017 at 3:46 | history | edited | Taylor | CC BY-SA 3.0 |
added 464 characters in body
|
| May 15, 2017 at 3:37 | history | edited | Taylor | CC BY-SA 3.0 |
added 464 characters in body
|
| May 14, 2017 at 22:13 | history | answered | Taylor | CC BY-SA 3.0 |