What is Big O of two loops

Question

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;
          }
    }

Did you know that you can empirically determine the complexity simply by adding a counter in the code and running it, then plotting the result? If you have a hunch for what the complexity is, this is a helpful way to confirm it. — that other guy, Feb 14 '22 at 21:58
It's O(j*n) and since j is a constant, you can drop j. So, the result is O(n). — Cheng Thao, Feb 14 '22 at 22:09
This code has **quadratic** time complexity. Declaration of variables **i** and **j** outside of the loop is unnecessary. — Alexander Ivanchenko, Feb 14 '22 at 23:21
@AlexanderIvanchenko You are right. I wasn't paying attention enough to see. — Cheng Thao, Feb 15 '22 at 00:10

score 1 · Answer 1 · answered Feb 14 '22 at 21:26

1

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)

answered Feb 14 '22 at 21:26

Gavin Haynes

1,721
11
21

What is Big O of two loops

1 Answers1