Determine run-time of an algorithm

Question

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?

Answer 1

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

Answer 2

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.