Thread: Big O Notation

I have some code snippets in which I have to find the run time using big O notation.


code frag 1:

Code:

void E(int array[], int N){
int i, j;
for(i=1; i<N-5; i++){

     for (j=i; j<i+5; j++)
     array[i] +=array[j];
   array[i] = array[i]/5;
}
}

I understand the simpler ones such as O(N) and O(N^2), but this seems to be slightly more complex.

could someone explain how we would arrive at an answer for this?

You need to count how many times you will add things in. How many times will each for loop run?

say if N was 10, the outside loop would run 5 times, and the inside loop would also run 5 times, so would it be O(5N)?

Originally Posted by bigparker

say if N was 10, the outside loop would run 5 times, and the inside loop would also run 5 times, so would it be O(5N)?

Because obviously 5 * 10 is 25.

The point of big O is, how does the number of steps change, when N changes.

N is the number of elements. You need to determine what is done for each element. But not with constants such as 10, but like "n²" or "n * log(n)".

if it was "j < n" or like that, the algorithm would run in O(n^2) time, since you have to do something for each element, which in turn is doing something for each element.