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