Sum of a sum [algorithm design and analysis]

Question

I'm studying the algorithm analysis of one piece of code, and I have to find the big-O notation of the sum of a sum.

$$g(n)=\sum^{n}_{i=0}\left(\sum^{n}_{j=i+1}O(1)\right)$$ $O(1)= c\times1$, thus $$g(n)=\sum^{n}_{i=0}\left[\sum^{n}_{j=i+1}(c\times 1)\right]$$

But I can't take it from here.

Any suggestion? thanks!

Answer 1

You can simply write $c$ instead of $(c \times 1)$, and then evaluate the sum. What kind of function of $n$ do you get?

Answer 2

What is $\sum_{j=i+1}^{n} c$? It evaluates to $c(n-i)$. We can then pull out the $c$ and evaluate $c\sum_{i=1}^{n} (n-i)$. You should be able to take it from here.

Note: With complexities, you can drop the constant. So with $O(1)$, you can simply replace it with $1$, and it won't change the complexity.