Infinite series from 2 to k

62 Views Asked by At

We know that that infinite series gives:

$$\sum_{i=1}^{k}i = k(k+1)/2$$

I am analyzing an algorithm that has complexity:

$$ n\sum_{i=2}^{k} i$$

My goal is to produce the tightest possible bound on this algorithm. Is it sound to say that the above sum is equivalent to:

$$ n*(k(k+1))\div2-1 $$

What is the best way to reduce my sum into a formula for analysis?

1

There are 1 best solutions below

0
On BEST ANSWER

Barring a mistake with the bracketing, what you wrote is correct. Since $\sum_{i=1}^{k}{i}=\frac{k(k+1)}{2}$,

$$ n\sum_{i=2}^{k}{i} = n(\sum_{i=1}^{k}{i} - 1) = n \cdot \left[\frac{k(k+1)}{2} - 1\right]$$

You can rearrange this a bit to get $\frac{1}{2}\left( nk^2 + nk - n \right)$ if that is any more useful.

You seem to have some confusion with terminology in your question. What you have is a finite sum, since you have $1+2+3+\ldots+k$ which is finitely many terms.

An infinite series is where we have the sum going to $\infty$, e.g. something like $\sum_{i=1}^{\infty}{\frac{1}{2^n}}$.