# BigO complexity

Page 1 of 1

## 3 Replies - 346 Views - Last Post: 31 January 2013 - 07:04 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=310443&amp;s=6076ec1ba045208bf6ad658b3ad3259e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ramiz127

Reputation: 0
• 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

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,173
• 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.

### #3 ramiz127

Reputation: 0
• 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;
}

```

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,173
• 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.