Anybody can explain how, summation of $1$ to $N$, can be replaced with integration and result leads to $(1/2)N^2$: $$ \sum_{i=1}^N i \sim \int_1^N x \ \mathrm{d}x \sim \frac{1}{2}N^2 $$
Note: Image is attached.
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ This might be useful:$$\sum_{i=1}^Ni=\frac12N(N-1)$$ So for large $N$, $\sum_{i=1}^Ni\approx \frac12N^2$ $\endgroup$– John DoeCommented May 7, 2017 at 18:05
-
$\begingroup$ The question is short that you should have formatted it. $\endgroup$– mlcCommented May 7, 2017 at 18:07
-
$\begingroup$ The summation in this comment should be $N(N+1)/2$ $\endgroup$– skuCommented May 8, 2017 at 15:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
As $N$ gets bigger, the interval between each $i$ in the summation, which is $1$ in this example, becomes extremely small with respect to $N$. Thus, for extremely large $N$, we can approximate the sum by integrating the term, as integration is the limit of summation when the distance between each value to be summed goes to zero. Hence,
$$\sum_{i=1}^N i \sim \int_1^N x \ \mathrm{d}x$$
Evaluating the integral to the right, we get
$$\frac{1}{2}N^2 - \frac{1}{2}N. $$
Similar to how 1 becomes extremely small with in comparison to $N$ for very large $N$, $N$ becomes very small in comparison to $N^2$ for very large N. Thus, the $N^2$ term dominates in the expression, and we can basically ignore the $N$ term. Thus, $$\frac{1}{2}N^2 - \frac{1}{2}N \sim \frac{1}{2}N^2.$$