Big O notation complexity in three cases

Question

Do following algorithms run in O(n) time?

1

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

    s=s+1
}

This is a O(n^2) since here performance directly proportional to the square of the size of the input data set N

2

 s=0
    for(i=0; i<n; i++)
    { if (i>20)
        for (j=0; j<n; j++)
        {
            s=s+i*j;
        }

        s=s+1
    }

3

 s=0
    for(i=0; i<n; i++)
    { if(i<4)
        for (j=0; j<n; j++)
        {
            s=s+i*j;
        }

        s=s+1
    }

Can you please explain how the if statement affects O(n)? In both cases (#2 and #3) first loop is O(n) and the second loop is going to run if N > 20 or N < 4 respectively. But how this affects complexity? Will these are still be O(n^2) with if i > 20 does 20^2 operations less and if i < 4 4^2 less? Also that Big O assumes that N is going to infinity?

Answer 1

2

Still O(N^2). The loop runs a total of

20 + (N - 20) * N iterations (and each iteration is constant) ==> O (N^2)

3

O(N). The loop runs a total of

N * 4 + (N - 4) iterations (and each iteration is constant) ==> O(N)