I am confused on the performance analysis of
binarySearch from the Collections
If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
I am not sure how to interpret this
I mean isn't it worse than simply traversing the linked-list and compare? We still get only
So what does this statement mean about performance? As phrased, I can not understand the difference from a plain linear search in the linked list.
What am I missunderstanding here?