Computation of Big O notation

52 Views Asked by At

I am reading some numbers theory texts, which involve estimation using big O. The steps I am confused about are $$ M \leq \sum_{\zeta_1<q\leq\zeta_2} \frac{2x}{(q-1)\log(x/q)} = O(\frac{x}{\log(x)}\sum_{\zeta_1<q\leq\zeta_2} \frac{1}{q}) = O(\frac{x}{\log^2(x)}\sum_{\zeta_1<q\leq\zeta_2}\frac{\log(q)}{q}). $$

where $\zeta_1 = x^{1/2}\log^{-2}(x), \zeta_2 = x^{1/2} \log(x).$

I know the definition of big O notation, so I tried to move the term independent of the $q$ outside the summation. In order to have $\frac{x}{\log(x)}$ outside, I try to use $\log(x/q) \geq \log(x/\zeta_2)$ and plug in value of $\zeta_2$ to bound the whole summation, but then I am stuck with the denominator. For the second equality, I can see why it might be true, but I cannot come up with a detailed reasoning.

Could anyone help me out? Thank you very much!

1

There are 1 best solutions below

0
On

Since big-O bounds are asymptotic, we can assume $x$ is sufficiently large that $\log x < x^{0.1}$. Then $x^{0.3} < \zeta_1 < x^{0.5}$ and $x^{0.5} < \zeta_2 < x^{0.6}$, so we have $x^{0.3} < q < x^{0.6}$ for every value of $q$ in the sum.

This means that $0.3 \log x < \log q < 0.6 \log x$, and also that $0.4 \log x < \log(x/q) < 0.7 \log x$. As a result, inside the big-O, we should feel free to replace $\log(x/q)$ by $\log x$, or $\log x$ by $\log q$, both in the numerator and in the denominator. (And that's what happens in the last step: we divided by $\log x$, but multiplied by $\log q$, which is equivalent to multiplication by a constant factor.)