Take the 2-minute tour ×
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.

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|improve this question
1  
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
1  
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
1  
Did you mean $\mathcal O(n^{k-1})$? –  Hagen von Eitzen Nov 1 '13 at 11:50
1  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.