# Big O notation for a small code segment

## Recommended Posts

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!

##### Share on other sites
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 by fiveworlds

##### Share on other sites
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 by Unity+

##### Share on other sites

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.

##### Share on other sites

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).

## Create an account

Register a new account