# How do you simplify this big O sum?

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?

-
Think for small values; e.g., with $k=2, 3$ and $n=1,2,3$. This should give a clue. – Doldrums Nov 1 '13 at 11:10
Could you clarify your question: $\mathcal{O}(i^{k-2})$ with respect to ...? – user64494 Nov 1 '13 at 11:22
...and observe that $\mathcal O$ is kinda "linear", i.e. $\sum \mathcal O(...) = \mathcal O(\sum ...)$ – AndreasT Nov 1 '13 at 11:22
Did you mean $\mathcal O(n^{k-1})$? – Hagen von Eitzen Nov 1 '13 at 11:50
The linearity is inherited by that of the limits. $f(n)\in\mathcal O(\alpha) + \mathcal O(\beta)$ means that $f=f_\alpha + f_\beta$ for some $f_\alpha\in\mathcal O(\alpha)$, $f_\beta\in\mathcal O(\beta)$; assuming wlog $\mathcal O(\alpha)\subseteq\mathcal O(\beta)$ $$\lim_{n\to\infty}\frac{f}\beta = \lim_{n\to\infty}\frac{f_\alpha}\beta + \lim_{n\to\infty}\frac{f_\beta}\beta \in\mathbb R$$ therefore $f\in\mathcal O(\beta) = \mathcal O(\alpha+\beta)$. This proves that $\mathcal O(\alpha)+\mathcal(\beta)\subseteq\mathcal O(\alpha+\beta)$. A similar reasoning proves the other inclusion. – AndreasT Nov 1 '13 at 12:31

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