Databases
StackOverflow2013
Postsdbo
POBig O Notation of a certain algorithm?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBig O Notation of a certain algorithm?
    primarykey
    data
    text
    <p>I have the following algorithm that determines the greatest common divisor of two numbers x and y. I need to find the big o notation that describes this algorithm and explain why, but I have no idea how to do this. </p> <p>Could someone please look at my code and explain what type of big oh notation it would be?</p> <pre><code> public void question1(int x, int y){ ArrayList divisorx = new ArrayList(); //the list of divisors of number x ArrayList divisory = new ArrayList();//divisors of number y ArrayList answerSet = new ArrayList();//the common divisors from both //divisorx and divisory for(int i=1; i&lt;=x; i++){//this loop finds the divisors of number x and //adds them to divisorx double remainder = x%i; if(remainder==0){ //i is a divisor divisorx.add(i); } } for(int i2=1; i2&lt;=y; i2++){//this loop finds the divisors of number y //and adds them to divisory double remainder2 = y%i2; if(remainder2==0){ //i2 is a divisor divisory.add(i2); } } int xsize = divisorx.size(); int ysize = divisory.size(); for(int i=0; i&lt;xsize; i++){//this massive loop compares each element of //divisorx to those of divisory to find common divisors. It adds those common //divisors to the arraylist answerSet for(int j=0; j&lt;ysize; j++){ if(divisorx.get(i)==divisory.get(j)){ //common divisor has been found //add it to an answer array answerSet.add(divisorx.get(i)); } } } Collections.sort(answerSet);//sorts the answerSet from smallest to greatest Object gcd = answerSet.get(answerSet.size()-1);//get the last element of the //arraylist, which is the gcd System.out.print("Your Answer: "+gcd);//print out the greatest common divisor } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USLuke Woodward
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POBig O Notation of a certain algorithm?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POBig O Notation of a certain algorithm?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHave a look at the loops and the Operations. E.g. you `sort` a collection sortingcosts at least *O(n log n)*
      singulars
      1. POBig O Notation of a certain algorithm?
      1. USMrSmith42
    2. COOne place to start is to count how many times each line of code is executed.. Many lines are only executed once, so you mostly need to pay close attention to loops. In this particular case, your "counting" will be in terms of x and y.
      singulars
      1. POBig O Notation of a certain algorithm?
      1. USCode-Apprentice
    3. COThe important thing when you compute something like this is to look at the number of bits that each number is. Doing the analysis in terms of the magnitude is trickier.
      singulars
      1. POBig O Notation of a certain algorithm?
      1. USEdvard Fagerholm
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload