# Can you explain me how this Big O notation is used?

So I was reading a book in analytic number theory and there was this claim $$\sum_{a\leq x} 1/a =\log x+O(1)$$ and since we kinda skipped these big $$O$$ notation problems at early uni days I got wondering how I can be sure in something like this?

I mean I can see how $$\sum_{a\leq x} 1/a \leq \log x$$ holds but how can I be sure that the rest is $$O(1)$$?

Also if I take $$\sum_{a\leq x} O(1)$$, $$O(1)$$ I can get out of the sum and the sum is something that is less than $$x$$ so $$O(x)$$ so that gives me $$O(1)O(x)$$ which is $$O(x)$$, am I correct?

• $$\log n = \int_1^n {\frac{{dx}}{x}} < \sum\limits_{k = 1}^n {\frac{1}{k}} < 1 + \int_1^n {\frac{{dx}}{x}} = 1 + \log n$$
– Gary
Jun 15 at 11:04
• Can you explain first how the first inequality holds and how this answers my question? Jun 15 at 11:11
• Note that $$\sum\limits_{k = 1}^n {\frac{1}{k}} = \sum\limits_{k = 1}^n {\int_k^{k + 1} {\frac{{dx}}{k}} } \ge \sum\limits_{k = 1}^n {\int_k^{k + 1} {\frac{{dx}}{x}} } = \int_1^{n + 1} {\frac{{dx}}{x}} = \log (n + 1) > \log n.$$ The inequalities show that $\sum\nolimits_{k = 1}^n {\frac{1}{k}} - \log n$ is bounded, i.e., $$\sum\limits_{k = 1}^n {\frac{1}{k}} = \log n + \mathcal{O}(1).$$
– Gary
Jun 15 at 11:16
• Does this help math.stackexchange.com/questions/4139408/…? Jun 15 at 13:57

To summarize the comments to this question and add one bit of extra info, the notation $$f(x) = O(g(x))$$ is defined to mean that $$\left| f(x)\right| \leq C g(x)$$, where $$C$$ is a constant independent of $$x$$. For your specific question, one needs to show that for some suitable constant $$C$$, we have $$\left| \sum_{a \leq x} \frac{1}{a} - \log x\right| \leq C.$$ From the comments provided by Gary, we have precisely this inequality with $$C = 1$$. In fact, one can use partial summation to deduce that $$\sum_{a \leq x} \frac{1}{a} = \log x + \gamma + O\left(\frac{1}{x}\right),$$ where $$\gamma$$ denotes the Euler-Mascheroni constant. In general, when dealing with the sums $$\sum_{a\leq x} f(a)$$ where $$f$$ is differentiable (or, say, continuously differentiable $$k$$ times), you should expect the sum above to be comparable to the integral $$\int_{1}^{x} f(t) dt.$$ Indeed, this is precisely the content of the Euler-Maclaurin summation formula.
By a more careful analysis, one can obtain an asymptotic expansion of the sum above with an arbitrarily small error term. For instance, if $$\psi(x) = \left\{ x\right\} - \frac{1}{2}$$, where $$\left\{ x\right\}$$ denotes the fractional part of $$x$$, then $$\sum_{a \leq x} \frac{1}{a} = \log x + \gamma - \frac{\psi(x)}{x} + O\left(\frac{1}{x^2}\right).$$