Determine the order of the following algorithm: 1.

int answer(int n){
 if ( 1 == n ) return 2;
 else return 2 * answer(n-1);
}

a O(1) b O(log n) c O(n) d O(n^2) e O(2^n) --- We began learning about the order of algorithms in my AP Java class the other day. Unfortunately, my fuckhole school put me a year behind in math. I''m finally begininng to understand all of this, but this question is still leaving me confused. I would hazard a guess to say the answer for this will be C. because the amount of steps per cycle increases only by one. Am i right? Also:

final int N = 100;

boolean[][] data = new boolean[N][N];

void invert(boolean[][] data){
 for ( int row = 0; row < N; row++ ){
  for ( int col = 0; col < N; col++){
   data [row][col] = ( 0 == data[row][col]);
  }
 }

A O(1) B O(log n) C O(n) D O(n^2) E O(2^n) -- For this second one i have not the slightest clue. Any help would be great, thanks.

It''s been awhile for me, but I would say that the first one would be O(n) and the second one O(n^2) since you have two nested loops.

The other posters are right. Unfortunately, they''re not always so simple. I don''t know if you learned the technical definition of big-O yet, but you have to be careful with more complex situations. In your first example, c, d, and e are all corrent answers. In this case, the number of times you perform the operation is exactly n. From the formal definition, there is some constant k, and some number of elements p (we actually used n naught, but I can''t type that), such that k*n > n for all n >= p. If k > 1 and p = 1, then is is true, and it is O(n). However, k*n^2 > n for all n >= p for k > 1 and p = 1, so it is also O(n^2). This is where it gets more complicated, because any big-O can encompass any larger big-O. For example, if you had:

for(int x = 0; x < n; x += 2){    doStuff();} 

This obviously executes n/2 times. However, you can still find k and p for both O(n) and (n^2). Generally however, you want the tightest bound, which is as the other posters said. Basically, you''re trying to find how many operations it would be if n was really big. n and n/2+1 may as well be the same when n = 1,000,000, at least in terms of running time. If you''re sorting some small amount of data, and you have an algorithm that''s O(n^2) and one that''s O(n*log(n)), it won''t really matter which you choose. However, when n is big, even though the O(n*log(n)) one may take longer to setup, it much more efficient on a large data set, which it what big-O trys to convey. Hopefully a bit of a more formal definition coupled with the other descriptions will help.

tj963

The order of the first one is O(C) and the order of the second is 0(n^2). The reason for this is because both of the statements in the first one are JUST statements and have constant running time, much like variable declarations.
The second one has two for loops, which makes it quadratic, or n^2. The ''while'' condition in the for loop gives you this. A normal for loop has linear running time (0(n)), so a nested for loop will be quadratic.

quote:Original post by Adam jo30
The order of the first one is O(C) and the order of the second is 0(n^2). The reason for this is because both of the statements in the first one are JUST statements and have constant running time, much like variable declarations.
The second one has two for loops, which makes it quadratic, or n^2. The ''while'' condition in the for loop gives you this. A normal for loop has linear running time (0(n)), so a nested for loop will be quadratic.

The first one is definitely not constant running time. Passing a value of 1 gives you dramatically different running time than passing 100.

/*This program finds the most frequently occuring value in a list of number stored in a text file, shortnum.txt.  If there are multiple answers, the algorithm will find only one of them.  The integers in the gile range from 1...M, and there are N values in the file*/import chn.util*;public class TestOrder{ public static void main(String [] args){  final int M = 100;  FileInput inFile;  int largestCount = Interger.MIN_VALUE;  int count, number, mod = 0;  for ( int loop = 1; loop <= m; loop++ ){   inFile = new FileInput("shortnum.txt");   count = 0;   while ( inFile.hasMoreTokens()){    number = inFile.readInt();    if( loop == number){     count++;    }   }   if ( count > largestCount ){    largetstCount = count;    mode = loop;   }   inFile.close();  } System.out.println("mode = " + mode );}

a N
b M
c N^2
d M^2
e M*N


-

Woo, wee thats a doozie

MrPoopypants,

Homework questions are not generally welcome in this forum. Keep in mind that this is a game development sight, not a homework help sight. Homework discussions are usually considered a misuse of expensive bandwidth and are often harmful to the potential intelligence of the person who asked the question. In very rare cases, homework questions are allowed to remain open----when the poster follows the guidelines provided in the forum FAQ. You have not followed the guidelines, and perhaps you are not familiar with them. You can find the full forum policy on homework here:

Forum FAQ

You will also find, in that FAQ, links to websites such as Dr. Math, that are more focused on homework. Please use these sites wisely!

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.