Is ArrayList an index of complexity N?

Question

I have N numbers in an arraylist. To get indexOf , the arraylist will have to iterate at most N times, so the complexity is O(N) , is this correct?

Answer 1

Java API Source

Yes, the difficulty is O (N).

The operations size, isEmpty, get, set, iterator and listIterator are performed in constant time. The add operation operates in amortized constant time mode, that is, adding O elements takes O (n) time. All other operations are performed in linear time (roughly speaking). The constant coefficient is not high compared to the constant for implementing LinkedList.

Answer 2

Yes, this is O (n), as it has to iterate over each item in the list in the worst case.

The only way to achieve better than this is to have some kind of structure on the list. The most typical example is viewing a sorted list using a binary search in O (log n) time.

Answer 3

Yes, that's right. The order is based on the worst case.

Answer 4

It's true. The best case is 1, so O (1), the middle case is N / 2, so O (N) and the worst case is N, so O (N)

Answer 5

100%, he needs to iterate over the list to find the correct index.

Answer 6

ArrayList is an array with many functions. Thus, the order of complexity of operations performed with an ArrayList is the same as for an array.

Answer 7

In the worst case, you find the item in the very last position that takes N steps, i.e. O (N). At best, the element you are looking for is the first, so the complexity is O (1). The average length is the average number of steps. If we do not have an additional context, then this can be done by 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, therefore O (n).

However, if you have large final data to work with, then you can calculate the exact average as described above.

In addition, you may have a context that can help you get extra accuracy in your calculations.

Example:

Consider an example where your array is ordered by frequency in descending order. In case your call to indexOf is use, then the most probable is the first, second, etc. If you have the exact frequency of use for each item, you can calculate the likely time to wait.