-1
$\begingroup$

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.

$\endgroup$
3

2 Answers 2

1
$\begingroup$

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 \ .$$

$\endgroup$
4
  • $\begingroup$ May I ask the silly question of how do I know the last term (the one with $\ln^8$) is $O(1)$? $\endgroup$
    – fox
    Jan 20 at 13:29
  • $\begingroup$ @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)$ $\endgroup$
    – SilvioM
    Jan 22 at 8:48
  • $\begingroup$ 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 $\endgroup$
    – fox
    Jan 23 at 11:55
  • $\begingroup$ @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)$. $\endgroup$
    – SilvioM
    Jan 23 at 12:15
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.