3 Replies - 201 Views - Last Post: 31 January 2013 - 07:04 PM Rate Topic: -----

#1 ramiz127  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 17-January 13

BigO complexity

Posted 30 January 2013 - 11:29 PM

What is the expected BigO Complexity of the following code?
  private static <ListType> void sort(ArrayList<ListType> list,
      Comparator<ListType> c) {
    for (int i = 0; i < list.size() - 1; i++) {
      int j, minIndex;
      for (j = i + 1, minIndex = i; j < list.size(); j++)
        if (c.compare(list.get(j), list.get(minIndex)) < 0){
          minIndex = j;}
      //swaping part
      ListType temp = list.get(i);
      list.set(i, list.get(minIndex));
      list.set(minIndex, temp);



Is This A Good Question/Topic? 0
  • +

Replies To: BigO complexity

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10376
  • View blog
  • Posts: 38,415
  • Joined: 27-December 08

Re: BigO complexity

Posted 31 January 2013 - 07:46 AM

The outer loop takes O(n) steps and the inner loop takes O(n) steps. What happens when you nest loops? You multiply the complexities. KYA's tutorial should help you learn how to analyze code as well.
Was This Post Helpful? 0
  • +
  • -

#3 ramiz127  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 17-January 13

Re: BigO complexity

Posted 31 January 2013 - 02:49 PM

Thank you, that was helpful. I have come across another problem. I know that the following code has a complexity of sqrt(N) I just don't know how to explain why it is. Can you please explain me the reason
public static <T> boolean binarySearch(ArrayList<T> list, T item, Comparator<? super T> cmp)
	{	int startIndex = 0;
		int endIndex = list.size() - 1;
		int midpoint = endIndex/2;
		
		while(endIndex > startIndex){
			if(cmp.compare(list.get(midpoint), item) == 0){
				return true;
			}
			else if(cmp.compare(list.get(midpoint), item) < 0){
				startIndex = midpoint + 1;
				midpoint = (endIndex + startIndex)/2;
			}
			else{
				endIndex = midpoint - 1;
				midpoint = (endIndex + startIndex)/2;
			}
		}
		//TODO: Fill in with a correct binary search implementation
		return false;
	}
	


Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10376
  • View blog
  • Posts: 38,415
  • Joined: 27-December 08

Re: BigO complexity

Posted 31 January 2013 - 07:04 PM

Binary search is actually O(log(n)). On each iteration, you are dealing with half of the list. So when you divide iteratively, it's O(log(n)). If you draw it as a Tree, you can more easily see the illustration.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1