Thread: Big O

Algorithm Form Running time

for(i=a; i<=b; i++){ 0(1)
//Loop body requiring
//Constant time
}


for(i=a; i<=N; i++){ 0(N) Linear time
//Loop body requiring
//Constant time
}

This is a example in a book but I do not see why the first loop is
faster then the second?

You need to remember that O notation isn't a measure

of speed but of rate of growth. If you look at the first one as N increases

the number of times the loop is excuted (b - a + 1) remains the same.

Nick,

Could you expand on that a little. I'm not following.

for(i=a; i<=N; i++) 0(N^2)-Quadratic time
for(j=b; j<=N; J++){
//Loop body requiring
//Constant time
}

for(i=a; i<=N; i++) { O(N*M)
//Loop body requiring
//time O(M)
}

I understand the first for loop and the Big O notation but I do not understand why the second for loop is (N*M)?

This information assumes that N is the unknown or variable quantity.

Code:

for(i=a; i<=N; i++) 0(N^2)-Quadratic time 
   for(j=b; j<=N; J++){ 
   //Loop body requiring 
   //Constant time 
}

This is O(N^2) because each loop of N runs N times regardless of what N is.

Code:

for(i=a; i<=N; i++) { O(N*M) 
   //Loop body requiring 
   //time O(M) 
}

This is based on the same principal as the first one except that M can be variable also. Generally this can be expressed as O(N^2), but since M doesn't have to be equal to N, it is usually more specifically expressed as O(N*M). When you are trying to graphically see which algorithm is better by plotting on a two-dimensional plane the Big-Oh expressions, you can't accurately plot y=NM like you are able to do with y=N^2.

Code:

for(i=a; i<=b; i++){ 0(1) 
   //Loop body requiring 
   //Constant time 
}

This code isn't based on N, so in terms of N it is constant time. The time doesn't vary based on N at all. Since the Big-Oh is usually based on N or one particular variable quantity, it is O(1). On the other hand, if you were to develop an actual expression to describe the runtime, it would be b-a+1. This just describes how many times the body of the loop will run for any integer values a and b.

Hopefully this clears up a little bit regarding the Big-Oh discussion.

Here are some more formal definitions but at this
point you probably should just look at a
procedure and guess without proving it.

http://www.ics.uci.edu/~lueker/23/notation.pdf
http://www.cs.hmc.edu/courses/2001/s...s140.lec01.pdf
http://www.cs.uky.edu/~jurek/cs315/n...s05102001.html