Complexité temporelle de contains(Object o), dans un ArrayList of Objects

Question

Comme le titre l'indique, je me demandais quelle est la complexité temporelle de la contains() d'unArrayList .

Answer 1

c'est O(n) pour ArrayList

Answer 2

ses O(n) . contains(Object o) est implémenté sur indexOf() qui prend O(n) . Donc la complexité de contains(Object o) est défensivement O(n)

En voici d'autres si besoin :

 add() - O(1)
add(index, element) – O(n)
get() – O(1)
set() – O(1)
remove() –  (n)
indexOf()` – O(n)