Q:

Understanding comparison using Big O notation

I was going through this heavily discussed and highly voted question on SO and stumbled across one comment that got 5 upvotes.
So I assume this was a great comment.But it got my head spinning at the same time. Can any one explain this comment? The comment says:

You can't compare big-O values directly without thinking about constant factors. For small lists (and most lists are small), ArrayList's O(N) is faster than LinkedList's O(1).

A:

all O(1) means is that it takes constant time, but not necessarily 1 unit of time.  So for a concrete example, let's say the LinkedList takes 3 seconds to access any element.  This is in constant time, but it is fairly slow.  It is not hard to imagine a situation where we have an Arraylist with O(n) access, but where n is small enough that no element would take more than 2 seconds to access.  In such cases, the ArrayList would actually be faster than the LinkedList.

A:

The definition of BigO means that you've defined a function where you've bounded the running time as a function of the input size, for all values greater than some constant factor.
What is a constant factor? Basicaly it's the part of the running time that doesn't depend on the input size. Lets say your linked list was stored in China. Even though it's O(1), every operation involves a flight to china. That's a constant factor, it never changes. However, the scalability of the algorithm is still O(1) because the flight to China is the same amount of time independent of the number of items in the list.
So yes, this statement is true in practice: "You can't compare big-O values directly without thinking about constant factors."
this statement is likely not true, it's implementation dependent: " For small lists (and most lists are small), ArrayList's O(N) is faster than LinkedList's O(1)."

