Question: 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?

Answer: 
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)
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.