Cik ilgs laiks nepieciešams meklēšanai (piemēram, izmantojot metodi contains) kolekcijās List un Set?

List gadījumā meklēšana ar contains ir aprēķināšanas sarežģītība O(n), kur n ir elementu skaits sarakstā. Tas ir tāpēc, ka sliktākajā gadījumā ir nepieciešams pārbaudīt visus saraksta elementus, lai noteiktu, vai meklētais elements ir.

Set gadījumā, meklēšana ar contains ir vidējā aprēķināšanas sarežģītība O(1). To sasniedz, izmantojot hash tabulu iekšējai elementu glabāšanai. Ideālā gadījumā (labas hash funkcijas un bez kolīzijām), meklēšana aizņem nemainīgu laiku. Sliktākajā gadījumā (daudzas kolīzijas), sarežģītība var tuvināties O(n), bet tas praksē ir reti.