Archived

This topic is now archived and is closed to further replies.

Order of Algorithms

This topic is 5116 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You are right about the first one, it''s O(N). It''s O(N) because the algorithm does something with N, decrements, and then repeats. This means that it''ll execute about N times.

The second example is O(N^2). This is so because:
The first loop will execute N times. For each time that loop executes, the inner loop will execute N times. So you''ve got N N''s (N+N+N+...+N), or N * N = N^2.

I hope that makes sense! If not, I''m sure someone else here will have sometime up in a few minutes.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

/*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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You''ve gotten help with one here already. At least show your attempt at working it out if you want assistence with the rest of your homework.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 5116 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.