Big O notation for a small code segment

[gate13]

What is the running time order of the following code fragment?

int sum = 0;

for(int i=0; i<10; i++)

for(int j=0; j<N; j++)

for(int k=N-2; k<N+2; k++)

sum = sum + k;

 

Is it O(N^2)?I am so sure!

[fiveworlds]

for(int i=0; i<10; i++)
    for(int j=0; j<N; j++)
        for(int k=N-2; k<N+2; k++)
                 sum = sum + k;

which is basically an overcomplicated while loop running sum a set number of times. So an easier way to run this would be.

sum=(N-2)*40*N;

So the number of times your code runs is calculated by 10*N*4

Edited May 9, 2015 by fiveworlds

[Unity+]

for(int i=0; i<10; i++)
    for(int j=0; j<N; j++)
        for(int k=N-2; k<N+2; k++)
                 sum = sum + k;

which is basically an overcomplicated while loop running sum a set number of times. So an easier way to run this would be.

sum=(N-2)*40*N;

So the number of times your code runs is calculated by 10*N*4

 

There is a difference between the exact run time and worst case scenarios in terms of Big-O notation.

 

If we remove all constants and replace them with c, we could get the following:

int sum = 0;
for(int i=0; i<10; i++)
    for(int j=0; j<N; j++)
        for(int k=N-2; k<N+2; k++)
                 sum = sum + k;

c+c*N((-N+2)+N+2) + c

 

And since we are only concerned with N:

 

c+c*N(4) + c

 

O(N)

 

So, this is O(n).

 

EDIT: Error caught by John, should be O(n).

Edited May 9, 2015 by Unity+

[John]

c+c*N(N+2) + c

 

And since we are only concerned with N:

 

N(N+2) = N^2 + 2N

 

O(N^2)

 

So, this is O(n^2).

I'd say O(n). The innermost loop only iterates through four values, since k starts at N - 2.

[Unity+]

I'd say O(n). The innermost loop only iterates through four values, since k starts at N - 2.

Oops, thank you for catching that. I didn't see that.

 

Nevermind, it is O(n).