gate13 Posted May 9, 2015 Share Posted May 9, 2015 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 More sharing options...

fiveworlds Posted May 9, 2015 Share Posted May 9, 2015 (edited) 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 Link to comment Share on other sites More sharing options...

Unity+ Posted May 9, 2015 Share Posted May 9, 2015 (edited) 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+ Link to comment Share on other sites More sharing options...

John Posted May 9, 2015 Share Posted May 9, 2015 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. 1 Link to comment Share on other sites More sharing options...

Unity+ Posted May 9, 2015 Share Posted May 9, 2015 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). Link to comment Share on other sites More sharing options...

## Recommended Posts

## 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