[ramiz127]

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

[macosxnerd101]

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.

[ramiz127]

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

[macosxnerd101]

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.