Complexity (beginner question)

What is the开发者_如何学编程 complexity of these statements?

for(int k = 1; k < n; k++)
    for(int i = 0; i < n-k; i++){
        //O(1) operation here
    }

Explanation appreciated.

---

First go in the outer loop, you do the operation n-1 times. Second go you do it n-2 times, ... Add those all up and you'll end up with (n)*(n-1)/2 operations.

To see that sum, write it from 1 to (n-1), then from (n-1) to 1 and add each term one by one.

  1   2   3 ... n-3 n-2 n-1
n-1 n-2 n-3 ...   3   2   1
---------------------------
  n   n   n       n   n   n

So 2 * sum = (n-1) * n.

So that's about n² in terms of complexity.