# Find the rate of growth for $\sum_{n=1}^N 1/n^p$ in term of big $O$ notation

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.

-

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.

-

$$O(N^{1-p})\qquad O(\log N)\qquad O(1)$$

-