0

I have two summations in a paper I'm reading

$$ \sum_{i=j}^{n-1}\frac{n}{i-1} $$ and $$ \sum_{i=j}^{n-1} \left(\frac{n}{i+1}\right)^2\left(1 - \frac{i+1}{n} \right) $$ and their big O notations are $n\log n + O(n)$ and $O(n^2)$ respectively. They are considering the case where $n \rightarrow \infty$. I just wanted some help understanding why these big O notations are as they are. I know that a harmonic series has growth of order $\log n$ but don't get where the extra $O(n)$ comes from. For the second one I tried to use the formula of a sum of squares but would that mean it should be $O(n^3)$, not sure where I'm going wrong. All help appreciated!

user729424
  • 5,061
hyperman
  • 21
  • This may help... The harmonic series is exactly equal to $n \log{n}$ plus an amount that is no more than a multiple of $n$... thus the $O(n)$ added to it. – Matt Groff Apr 12 '20 at 00:17

1 Answers1

1

$ \textbf{Lemma :} $

If $ p $ is an integer, and $ f:\left[p,+\infty\right)\rightarrow\mathbb{R}_{+} $ is continuous and decreasing, then there exists a constant $ \ell $ such that : $$ \sum_{k=p}^{n}{f\left(k\right)}=\int_{p}^{n}{f\left(x\right)\mathrm{d}x}+\ell+\underset{\overset{n\to +\infty}{}}{\mathcal{o}}\left(1\right) $$

$ \ $

$ \textbf{Hint}$ (To prove the previous lemma) $\textbf{:}$

It is possible to prove that the sequence $ \left\lbrace\sum\limits_{k=p}^{n}{f\left(k\right)}=\int\limits_{p}^{n}{f\left(x\right)\mathrm{d}x}\right\rbrace_{n} $ is convergent by proving that it is monotone and bounded.

Denoting $ H_{n}=\sum\limits_{k=1}^{n}{\frac{1}{k}} $, by using the previous lemma, we have : $$ H_{n}=\ln{n}+\gamma+ \underset{\overset{n\to +\infty}{}}{\mathcal{o}}\left(1\right)=\ln{n}+\underset{\overset{n\to +\infty}{}}{\mathcal{O}}\left(1\right) $$

Let $ j $ be a positive integer, we have : $$ \sum_{i=j}^{n-1}{\frac{n}{i-1}}=nH_{n-2}-nH_{j-2}=n\left(\ln{\left(n-2\right)}-H_{j-2}+\underset{\overset{n\to +\infty}{}}{\mathcal{O}}\left(1\right)\right)=n\ln{n}+\underset{\overset{n\to +\infty}{}}{\mathcal{O}}\left(n\right) $$

For the second one, we have, for some integers $ n,j $, the following : $$ \small\sum_{i=j}^{n-1}{\left(\frac{n}{i+1}\right)^{2}\left(1-\frac{i+1}{n}\right)}\leq n^{2}\sum_{i=0}^{n-1}{\left(1-\frac{i+1}{n}\right)}=n^{2}\sum_{i=1}^{n}{\left(1-\frac{i}{n}\right)}\leq n^{3}\int_{0}^{1}{\left(1-x\right)\mathrm{d}x}=\frac{n^{3}}{2} $$

Thus : $$ \sum_{i=j}^{n-1}{\left(\frac{n}{i+1}\right)^{2}\left(1-\frac{i+1}{n}\right)}=\underset{\overset{n\to +\infty}{}}{\mathcal{O}}\left(n^{3}\right) $$

CHAMSI
  • 8,333