Kiek laiko užtrunka paieška (pavyzdžiui, naudojant metodą contains) sąrašo ir rinkinio kolekcijose?

List atveju, paieška naudojant contains turi skaičiavimo sudėtingumą O(n), kur n yra sąrašo elementų skaičius. Tai yra todėl, kad blogiausiu atveju, reikia peržiūrėti visus sąrašo elementus, kad būtų nustatyta, ar ieškomas elementas yra.

Set atveju, paieška naudojant contains turi vidutinį skaičiavimo sudėtingumą O(1). Tai pasiekiama naudojant maišos lentelę vidiniam elementų saugojimui. Idealiu atveju (gera maišos funkcija ir be kolizijų), paieška užima pastovų laiką. Blogiausiu atveju (daug kolizijų), sudėtingumas gali priartėti prie O(n), tačiau tai yra retai praktikoje.