What is Big O of two loops-CodePudding

I am trying to find the Big-O for the Summing function. I know the two loops usually mean that N^2 run time but this is just one N but j is running many more than N itself.

int Summing( int n )
{
    int i 
    int j
    int s = 0;
    for(i=0; i < n; i  ){
        for(j=0; j < i; j  ) {
            s  = i*i;
          }
    }

CodePudding user response：

You can calculate the exact time the inner loop takes as a function of i and then sum it up over all values that i takes.

Here the number of times the innermost section is run is 0 1 2 ... (n-1) = (n-1)*n/2 = (n^2)/2 - n/2 which is O(n^2)

CodePudding user response：

You can see this thread for a more detailed view of the algorithm's complexity.