1

Probably a stupid question but I don't get it right now. I have an algorithm with an input n. It needs n + (n-1) + (n-2) + ... + 1 steps to finish. Is it possible to give a runtime estimation in Big-O notation?

user4811
  • 133

2 Answers2

3

Indeed, it is. Since we have $$n+(n-1)+(n-2)+\cdots+1=\frac{n(n+1)}2,$$ then you should be able to show rather readily that the runtime will be $\mathcal{O}(n^2)$.

Cameron Buie
  • 102,994
  • face palm Thanks!!! – user4811 Nov 01 '13 at 22:11
  • Maybe it's because I'm slow, but I don't understand how you got $\frac{n(n+1)}{2}$ from that sequence. I also don't get how you knew it was O(n^2). – David G Sep 08 '14 at 18:52
  • @David: That's a well-known closed form for the sum of the first $n$ positive integers. A quick geometric proof is to imagine stacking squares: first a stack of one square, next to a stack of two, next to a stack of three, and so on, until we have $n$ stacks, forming a jagged triangle. If we did that again, we'd need twice as many squares, and rotating the second arrangement a half turn and placing it on top of the first, we have an $n$ by $n+1$ rectangle. As for the other bit, what do you know about big-O notation? – Cameron Buie Sep 09 '14 at 13:13
  • @CameronBuie I'm just starting to learn big-O. From what I've read, it's an approximation of how an algorithm scales in proportion to its input size. I haven't gotten as far such that I would understand how you knew the algorithm was O(n^2) though. – David G Sep 09 '14 at 13:58
  • @David: I happened to know that a polynomial's "big-O" is always its highest order exponent. So, for example, here we have $\frac12n^2+\frac12n.$ The quadratic term has the highest degree, so the polynomial is $\mathcal O(n^2).$ To prove it, we need only find a positive constant $M$ such that for large enough $n,$ we always have $$\left|\frac{n(n+1)}2\right|\le M\left| n^2\right|.$$ It turns out that $M=1$ works for all $n\ge 1.$ – Cameron Buie Sep 09 '14 at 17:33
1

There are $n$ terms in your series, and each term is of the order $n$ at maximum. Therefore the operation takes on the order of $O(n^2)$ steps.

rgettman
  • 764