JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Justify the O(n^2) statement in the list implementation | Reply
public void Show(List l) {
for (int i = 0; i < l.size(); i++) {
System.out.println (l.get(i));
}
}

In reference to http://java.sun.com/j2se/1.4.2/docs/api/java/util/RandomAccess.html

Its clear that
for (int i=0, n=list.size(); i < n; i++)
list.get(i);


runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
Can you justify the above ..........
Re: Justify the O(n^2) statement in the list implementation (response to post by shantanu.gg) | Reply
What you are linking to does not state that the first loop is faster than the second. It says, you should do a comparison, and if normally the first loop is faster, then you should implement the interface RandomAccess for your list. As an example it says that LinkedList has O(n^2) complexity for the first loop, and therefore normally the second loop should be faster for it.
RSS