CODEWITHSUNDEEP
javaalgorithmbig-o
user1639780
user1639780

Reputation:

Big O Notation of a certain algorithm?

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.

Could someone please look at my code and explain what type of big oh notation it would be?

     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<=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<=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<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<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
 }

Upvotes: 2

Views: 556

Answers (3)

Simon
Simon

Reputation: 5402

First loop is done exactly X times.
Second loop Y times.
Third loop for sure less than (X/2 + 1) * (Y/2 + 1) times (since a number N can have at most N/2 + 1 divisors). So the worst case is O(XY/4) = O(XY).
The same for the size of the list answerSet, that can have at most XY/4 elements. Finally sorting is done in O(nlogn) (according to javadoc), that is, in your case, O(XYlog(XY)).
So the final complexity is O(X + Y + XY + XYlog(XY)) = O(XYlog(XY)).
If you want to express the complexity with only a generic N, then it is O((N^2)logN), where N = max(X, Y).

Upvotes: 0

Khaur
Khaur

Reputation: 770

First two loops have cost O(X) and O(Y), respectively.

Number of divisors of N is O(sqrt(N)) (see comments), so xsize and ysize are O(sqrt(X)) and O(sqrt(Y)).

Your last loop therefore has cost O(sqrt(X).sqrt(Y)).

answerSet has size O(min(sqrt(X),sqrt(Y))) since it is the intersection of divisorx and divisory.

You perform a sort on answerSet, which is O(min(sqrt(X),sqrt(Y)) log(min(sqrt(X),sqrt(Y)))

All of those are O(X+Y), so total complexity is O(X+Y).

Upvotes: 2

Konstantin Dinev
Konstantin Dinev

Reputation: 34895

The largest complexity is the two nested for-loops that you have. Big O is order and means it is the complexity relative to the input size. Here your input size is number of divisors which you find in linear time (1 for-loop each) meaning n + n or O(n). The sorting in your example is usually of average complexity of n*log(n). Your nester for-loops are square meaning O(n^2). Your order is then the O(n^2) because this is the largest complexity in computation. We take the largest degree in the polynomial expression that we get of adding all the complexities so O(n^2 + n*log(n) + 2n) which is 2nd degree polynomial and thus ~ O(n^2).

It should be noted that the order is the larger complexity of space and time. So if memory usage complexity is larger than computational complexity then that takes over.

Upvotes: 1

Related Questions