I have N numbers in arraylist. To get the indexOf, arraylist will have to iterate maximum N times, so complexity is O(N), is that correct?
asked Jan 27, 2014 at 18:14
-
The worst case complexity is O(N), but the typical complexity is also O(N) as it will have to search half way on average. c.f. HashMap.get() has a typical complexity of O(1) but a worst case complexity of O(N).Peter Lawrey– Peter Lawrey2014-01-27 19:04:23 +00:00Commented Jan 27, 2014 at 19:04
Add a comment
|
7 Answers
Source Java API
Yes,Complexity is O(N).
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
Comments
Yes it's O(n) as it needs to iterate through every item in the list in the worst case.
The only way to achieve better than this is to have some sort of structure to the list. The most typical example being looking through a sorted list using binary search in O(log n) time.
answered Jan 27, 2014 at 18:49
3 Comments
Lajos Arpad
It does not have to iterate every item of the list. If iterates them sequentially and when the first is found, it will return the index.
Daniel Imms
@LajosArpad clarified the first sentence.
Lajos Arpad
Acknowledged :)
Yes, that is correct. The order is based off the worst case.
Comments
100%, it needs to iterate through the list to find the correct index.
answered Jan 27, 2014 at 18:17
Comments
It is true. Best Case is 1 so O(1), Average Case is N/2 so O(N) and Worst Case is N so O(N)
1 Comment
Lajos Arpad
Actually, the average case is (N + 1) / 2.
In the worst case you find the element at the very last position, which takes N steps, that is, O(N). In the best case the item you are searching for is the very first one, so the complexity is O(1). The average length is of the average number of steps. If we do not have further context, then this is how one can make the calculations:
avg = (1 + 2 + ... n) / n = (n * (n + 1) / 2) / n = (n + 1) / 2
If n -> infinity, then adding a positive constant and dividing by a positive constant has no effect, we still have infinity, so it is O(n).
However if you have a large finite data to work with, then you might want to calculate the exact average value as above.
Also, you might have a context there which could aid you to get further accuracy in your calculations.
Example:
Let's consider the example when your array is ordered by usage frequency descendingly. In case that your call of indexOf is a usage, then the most probable item is the first one, then the second and so on. If you have exact usage frequency for each item, then you will be able to calculate a probable wait time.
answered Jan 22, 2017 at 14:00
Comments
An ArrayList is an Array with more features. So the order of complexity for operations done to an ArrayList is the same as for an Array.
answered Jan 27, 2014 at 18:47
