BigOh - How to determine the upper bound dealing with eccentric series?

Question

I would like to know what is the way to determine the upper bound of a series in BigOh terms.

For example, suppose the following series is given:

2 + 6 + 10 + 14 + ..... + ((4 * n) - 2)

How can I find out what is the upper bound of this series in Big-Oh terms?

Thank you very much.

Answer 1

You have to estimate the general term, throwing away some terms that are negligible and multiplicative constants.

In your example, you want to estimate $\sum_{i=1}^n (4i-2)$. This is equal to $4(\sum_{i=1}^n i)-2n=4\frac{n(n+1)}2-2n=2n^2=O(n^2)$ (it is even $\Theta(n^2)$)