June 4, 2013

Myth For Loop O(n) but O(n^2)

What's the time complexity of
for(int i=0; i < linkedlist.size(); i++){
     System.out.println(linkedlist.get(i));
} 

Contrary to the notion of that a simple for loop should be O(n), the above example is O(n^2). The reason being
is that for each iteration we need to go through the whole linked list one by one to get that specific index.

Solution:  Always use an iterator to avoid getting trapped in implementation details of a collection and let the iterator efficiently iterate through the whole thing.

No comments:

Post a Comment