2
$\begingroup$

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])
| cite | improve this question | |
$\endgroup$
4
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Aug 4 '18 at 13:09
  • $\begingroup$ 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. $\endgroup$ – Elliot Rodriguez Aug 4 '18 at 13:23
  • 1
    $\begingroup$ @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. $\endgroup$ – Daniel Mroz Aug 4 '18 at 13:38
  • 1
    $\begingroup$ @ElliotRodriguez Search about Carl Frederich Gauss's (alleged) story of (re)inventing this formula (at the age of five)! $\endgroup$ – xuq01 Aug 4 '18 at 16:06
  • $\begingroup$ @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*}$$ $\endgroup$ – David Richerby Aug 4 '18 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.