# Why is this n^2 growth?

I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading:

"... performs of the order of $n^2$ steps on a sequence of length $n$."

Could someone please explain how this is calculated in the following code, which is also taken from the book?

If I print out the statements when the lines are executed, it first executes $n$ steps, then decreases $n-1$ steps for each loop iteration until it reaches $0$. This does not seem like exponential growth to me. Why does this grow at $n^2$?

dataset = [3,1,2,7,5]
product = 0

# algorithm begins here
for i in range(len(dataset)):
for j in range(i + 1, len(dataset)):
product = max(product, dataset[i]* dataset[j])


Because $n + (n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n+1)}{2} \in \mathcal{O}(n^2)$.

Note that $n^2$ is polynomial, not exponential (that would be $2^n$ for example).

• In fact, $\frac{n(n+1)}{2} = \Theta(n^2)$, which is why it is stated that the number of steps is of order $n^2$. Aug 4, 2018 at 13:09
• So - I understand my error in thinking it was exponential, and I understand how n^2 is derived (distribute n and drop the lowest order constant), but I am not quite clear on how n + (n - 1)... 2 + 1 evaluates to that fraction? Pointing me to a resource for further research would be terrific. I am having trouble wrapping my head around how algorithms end up being evaluated as theta, O, and omega based on how they are written and steps they perform on input. Aug 4, 2018 at 13:23
• @ElliotRodriguez You can prove the identity $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ by induction on $n$ (here is a full proof). It's a good one to remember! When it comes to determining the complexity of algorithms I always find it helpful to trace through a few small cases first. Aug 4, 2018 at 13:38
• @ElliotRodriguez Search about Carl Frederich Gauss's (alleged) story of (re)inventing this formula (at the age of five)! Aug 4, 2018 at 16:06
• @DanielMroz Rather than using induction, it's much easier to just observe that the sum is \begin{align*}\tfrac12(&1+\dots+n + \\&n + \dots +1)\\&\quad = \tfrac12\big((1+n) +(2+ n-1) + (3+n-2) + \dots + (n+1)\big)\\ &\quad = \tfrac12n(n+1)\,.\end{align*} Aug 4, 2018 at 19:39