TITLE: Find the rate of growth for $\sum_{n=1}^N 1/n^p$ in term of big $O$ notation
QUESTION [0 upvotes]: Find the rate of growth for 
$$
\sum_{n=1}^N \frac{1}{n^p}
$$ 
in term of big $O$ notation for the three cases $0 < p < 1$, $p=1$ and $p>1$.
It seems the question can be approached by viewing the sum as a taylor series.
But I'm not sure how to do it.

REPLY [3 votes]: For $p>1$, $\displaystyle \sum_{n=1}^{\infty} \dfrac1{n^p}$ converges i.e. $\displaystyle \sum_{n=1}^{N} \dfrac1{n^p} = \mathcal{O}(1)$
For $p=1$, $\displaystyle \sum_{n=1}^{\infty} \dfrac1{n}$ diverges like $\log n$ i.e. $\displaystyle \sum_{n=1}^{N} \dfrac1{n} = \log(N) + \gamma + \mathcal{O}(1/N)$
For $p<1$, $\displaystyle \sum_{n=1}^{\infty} \dfrac1{n^p}$ diverges like $N^{1-p}$ i.e. $\displaystyle \sum_{n=1}^{N} \dfrac1{n^p} = \dfrac{N^{1-p}}{1-p} + $ lower order terms.
All these can be obtained by comparing $\displaystyle \sum_{n=1}^{\infty} \dfrac1{n^p}$ with $\displaystyle \int_{x=1}^{\infty} \dfrac{dx}{x^p}$
You can make use of Euler-Maclaurin to get more accurate expansions and better error bounds.

REPLY [2 votes]: $$O(N^{1-p})\qquad O(\log N)\qquad O(1)$$
{"set_name": "stack_exchange", "score": 0, "question_id": 215223}