# 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$. – Yuval Filmus Aug 4 '18 at 13:09
• @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. – Daniel Mroz Aug 4 '18 at 13:38
• @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*} – David Richerby Aug 4 '18 at 19:39