Jump to content

Big O notation for a small code segment


gate13

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!

Link to comment
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
Link to comment
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+
Link to comment
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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.