See also GeometricSums .

Here we explain by example a simple way to get an upper bound on a sum.

For example, consider the sum

- 1+2+...+n = ∑
_{i=1..n}i.

We can bound this sum from above as follows:

- 1+2+...+n = ∑
_{i=1..n}i. - ≤ n+n+...+ n (n times)
- = ∑
_{i=1..n}n = n*n = n^{2}.

Thus, the sum is O(n^{2}).

In general, a sum of n terms is at most n times the maximum term.

We can use a similar trick to bound the sum from below. We use the fact that the sum is at least the sum of its n/2 largest terms:

- 1+2+...+n = ∑
_{i=1..n}i - ≥ n/2+(n/2+1)+...+ n = ∑
_{i=n/2..n}i - ≥ n/2+n/2+...+ n/2 (n/2 times)
- = ∑
_{i=n/2..n}n/2 - = (n/2)*(n/2) = n
^{2}/4.

Thus, the sum is Ω(n^{2}).