I have a function $$f$$ such that is the sum of big O terms, such as

$$f=\left[\sum_{i=1}^x \frac{1}{i}\right] +O\left(\frac{\ln^4 x}{x}\right)+O\left(\frac{\ln^4 x-1}{x-1}\right)+O\left(\frac{\ln^4 x-2}{x-2}\right)+\ldots$$

where $$x$$ is a positive integer. Am I correct in that I can simply write

$$f=\left[\sum_{i=1}^x \frac{1}{i}\right] + O\left(\frac{\ln^4 x}{x}\right)$$

because I just need to write the bigger value for the big O, in this case being $$\frac{\ln^4 x}{x}$$?

Any intuitive, even informal answer would be welcome.

• – D.W.
Commented Jan 15 at 6:08
• Try adding parenthesis to the argument of the summation, it is not clear what you are writing Commented Jan 15 at 13:56
– fox
Commented Jan 15 at 16:16

It is not correct because you don't have a constant number of terms in your sum. Indeed, your sum has $$\ln^4 x$$ terms (assuming it stops when the numerator is $$0$$).

Actually the smaller terms may have an impact. However we can bound it.

Let's start by rewriting the sum: $$\sum_{i=0}^{\ln^4 x -1} \frac{\ln^4 x-i}{x-i} = \sum_{i=1}^{\ln^4 x} \frac{i}{x-\ln^4 x + i} .$$

Now, we have: $$\sum_{i=1}^{\ln^4 x} \frac{i}{x-\ln^4 x + i} \leq \sum_{i=1}^{\ln^4 x} \frac{i}{x-\ln^4 x } = \frac{1}{x-\ln^4 x }\sum_{i=1}^{\ln^4 x} i = O\left( \frac{\ln^8 x}{x-\ln^4 x} \right) \ ,$$ where we used a smaller denominator in order to have the inequality and then we used the Gauss formula for the sum of the first $$\ln^4 x$$ integers and passed to the asymptotic notation in order to get rid of constants and lower-order terms.

Now, this term is actually $$O(1)$$, so this sum has no impact on the overall asymptotic value of: $$\sum_{i=1}^{x} \frac{1}{i} \geq 1 \ .$$

• May I ask the silly question of how do I know the last term (the one with $\ln^8$) is $O(1)$?
– fox
Commented Jan 20 at 13:29
• @fox it is $O(1)$ because asymptotically $\frac{\ln^8 x}{x-\ln^4 x} \to 0$. So, we can actually say more, i.e. it is also $o(1)$ Commented Jan 22 at 8:48
• I see, thanks. But can't you say instead that $O\left(\frac{\ln^4 x}{x}\right)$ is$O(1)$ from the beginning and then just add a bunch of $O(1)$'s? @SilvioM
– fox
Commented Jan 23 at 11:55
• @fox it's not enough because you are not adding a constant quantity of $O(1)$, but $\ln^4 x$ of them. So, in this way you can only say that these terms together are $O(\log^4 x)$. Instead, we showed that all the terms together are still $O(1)$. Commented Jan 23 at 12:15

You can’t add an infinite number of big-Os.

O(f(x)) is limited by f(x), multiplied by some constant c. If you have 100 Big-Os then they all have different constants, so you can just take the largest.

But with an infinite number of Big-Os, these constants could grow without any limit, so there is no single c that limits the infinite sum.

For a particular sum, if you have the actual terms, and not just big-O, then you may be able to prove some bound. For example if you can show that there is a constant c that works for all terms. But not if all you know is that each term is limited with some constant.