Wie lange dauert die Suche (z.B. mit der Methode contains) in den Collections List und Set?

Für List hat die Suche mit contains eine rechnerische Komplexität von O(n), wobei n die Anzahl der Elemente in der Liste ist. Dies liegt daran, dass im schlimmsten Fall alle Elemente der Liste durchlaufen werden müssen, um die Existenz des gesuchten Elements zu bestimmen.

Für Set hat die Suche mit contains eine durchschnittliche rechnerische Komplexität von O(1). Dies wird durch die Verwendung einer Hashtabelle für die interne Speicherung der Elemente erreicht. Im Idealfall (gute Hash-Funktion und keine Kollisionen) dauert die Suche eine konstante Zeit. Im schlimmsten Fall (viele Kollisionen) kann die Komplexität O(n) annähern, was in der Praxis jedoch selten vorkommt.