Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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