Timeline for How did they cancel out O-terms in this fraction?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2018 at 7:03 | comment | added | ShreevatsaR | The assumption that $f_2$ is nonnegative may or may not be a big one, depending on how the expression in the LHS of the question was obtained. Note that the formula in the question is true regardless of whether $f_2$ is negative or not, and the bulk of Yuval's answer is concerned with proving it without making this assumption. (With this assumption, the $$\frac{2\ln(2N)+O(1)}{\ln N+O(1)} = 2 + O\left(\frac{1}{\log N}\right)$$ part of the question essentially gets replaced by the task of proving that $$\frac{2\ln(2N) + O(1)}{\ln N} = 2 + O\left(\frac{1}{\log N}\right)$$ which is much easier.) | |
| Feb 24, 2018 at 23:06 | comment | added | Raphael | @YuvalFilmus Very true, thanks. Fixed; it even got simpler. | |
| Feb 24, 2018 at 23:06 | history | edited | Raphael | CC BY-SA 3.0 |
new proof
|
| Feb 24, 2018 at 22:02 | comment | added | Yuval Filmus | Your first inequality doesn't follow, since we have big O in the denominator. You get an upper bound on both numerator and denominator, but this doesn't translate to an upper bound on the fraction. | |
| Feb 24, 2018 at 21:41 | history | edited | Raphael | CC BY-SA 3.0 |
added 149 characters in body
|
| Feb 24, 2018 at 21:35 | history | answered | Raphael | CC BY-SA 3.0 |