algorithm efficiency

Question

for (int i=1;i<=n;i++){
    for (int j=i;j<=n;j++){
        do_something
    }
}

I need to calculate how many times the "do something" step happens.

I started like so:

$\sum _{i=1}^n\:\sum _{j=i}^n\:1$

I got stuck here trying to open the inner sum. I know that the algorithm is O(n^2) but I find it hard to prove it.

Answer 1

$$\begin{align}\sum _{i=1}^n\:\sum _{j=i}^n\:1&=\sum_{i=1}^n(n-i+1)\\&=n\sum_{i=1}^n1-\sum_{i=1}^ni+\sum_{i=1}^n1\\&=n^2-\frac{n(n+1)}2+n\\&=\frac{n^2}2+\frac {n}2\end{align}$$