How do you simplify this big O sum?

Question

I saw someone interpret $\sum_{i=1}^{n}\mathcal{O}\left(i^{k-2}\right)$ as $\mathcal{O}\left(n^{k-1}\right)$. Is this right? If so, can you explain?

Answer 1

This is not quite true in this simplicity or at least depends on interpretation and context. One might interprete the statement as follows: Suppose that for each $n\in\mathbb N$ we have a function $f_n\colon \mathbb N\to\mathbb R$. Then we can define $f\colon \mathbb N\to \mathbb R$, $n\mapsto\sum_{i=1}^n f_i(n)$. Now if $f_n(x)=O(x^k)$ as $x\to \infty$ it does not follow that $f(x)=O(x^{k+1})$ as $x\to\infty$. For example, let $$f_i(n)=\begin{cases}n!&\text{if }n=i\\0&\text{otherwise}.\end{cases}$$ Then $f_i(n)=O(1)$ as $n\to\infty$ and $f(n)=n!$.

On the other hand, assume we have $g\colon\mathbb N\to\mathbb R$ and define $f\colon \mathbb N\to \mathbb R$, $n\mapsto\sum_{i=1}^n g(i)$. Now if $g(x)=O(x^k)$ as $x\to\infty$ we have $f(x)=O(x^{k+1})$ as $x\to\infty$. Indeed, assume $|g(x)|<cx^k$ for $x>N$. Then with $A=\left|\sum_{i=1}^Ng(i)\right|$ we have $$|f(x)|<A+\sum_{i=N+1}^n |g(i)|<A+c\sum_{i=N+1}^ni^k\le A+c(n-N)n^k<(c+A)n^{k+1}$$ for $n>N$.