2

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 }
Improve this question
4
  • Have a look at the loops and the Operations. E.g. you sort a collection sortingcosts at least O(n log n) Commented Jan 10, 2013 at 21:13
  • One 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. Commented Jan 10, 2013 at 21:13
  • The 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. Commented Jan 10, 2013 at 21:15
  • There are many operations that can be cleaned very easily in the above algorithm. For example rather than going from 1->x you can do x->2. That will eliminate the nested loop and replace sort by a small merge-like operation. Even if you don't implement the Euclidean method the current code seems like a way to slow down the blunt way as much as possible. Commented Jan 10, 2013 at 21:50

3 Answers 3

Reset to default
2

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

14 Comments

You're not taking into account the sort at the end.
Re-edited, as answerSet is O(N), the sort is O(N log N) which is lower than O(N²)
Edited once more, with a closer bound on the number of divisors
The number of divisors of N is not sqrt(N). Take 2: it has 2 divisors (1 and 2).
Big O notation is about asymptotical behaviour
|
1

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.

Improve this answer

4 Comments

You forgot the sort on answerSet as well
Sure that's usually nlog(n) I will add it.
Thank you for the quick response. However, I thought that because Big O looked at the worst-case, it would see that the Collections.sort() has a run time that represents O(nlog(n)). So wouldn't the final answer really be O(nlog(n))?
@GeorgioMahugana The O(n²) term beats the O(n log n) term. However with closer bounds neither of those terms end up being dominant (see my answer). Also note that you can apply Big O notation to other kinds of complexity analysis than worst-case, e.g best-case complexity.
0

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).

Improve this answer

2 Comments

If you look at the third loop on a semantic level, you'll see that you can get a closer min(X,Y) bound on answerSet
@Khaur Yes, I saw and I deleted my previous comment. Anyway, according to what you are saying, the complexity is O(X + Y + XY + NlogN). How can you compare XY and NlogN?