Complexity of two imbricated loops

Question

I have this algorithm (in c code for convenience):

int algo(int *T, int size)
{
   int n = 0;

   for (int i = 1; i < size; i++) {
       for (int j = i; j < size; j++) {
           n += (T[i] * T[j]);
       }
   }

   return n;
}

What is this algorithm's time complexity?

My bet is it is n * log (n) since we have two imbricated iterations on the size length one time, and onsize - i the second time, but I am not sure.

A formal proof of the complexity is welcome!

Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Paul Hankin, Jan 12 '17 at 04:00

score 3 · Accepted Answer · answered Jan 12 '17 at 02:25

This is an O(N²) algorithm.

First iteration of the outer loop runs N-1 times
Second iteration of the outer loop runs N-2 times
Third iteration of the outer loop runs N-3 times
...
Last iteration of the outer loop runs 1 time

The total number of times is (N)+(N-1)+(N-2)+...+1, which is the sum of arithmetic progression. The formula for computing the sum is N*(N-1)/2, which is O(N²).

Complexity of two imbricated loops

1 Answers1