Hoe lang duurt het zoeken (bijvoorbeeld met de contains-methode) in de collecties List en Set?

Voor List heeft zoeken met contains een computationele complexiteit van O(n), waarbij n het aantal elementen in de lijst is. Dit komt doordat in het ergste geval alle elementen in de lijst moeten worden doorlopen om te bepalen of het gezochte element aanwezig is.

Voor Set heeft zoeken met contains een gemiddelde complexiteit van O(1). Dit wordt bereikt door gebruik te maken van een hashtabel voor de interne opslag van de elementen. In het ideale geval (goede hashfunctie en geen botsingen) kost zoeken constante tijd. In het slechtste geval (veel botsingen) kan de complexiteit dicht bij O(n) komen, maar dit komt zelden voor in de praktijk.