Cât timp durează căutarea (de exemplu, utilizând metoda contains) în colecțiile List și Set?

Pentru List, căutarea folosind contains are o complexitate computațională de O(n), unde n este numărul de elemente din listă. Acest lucru se datorează faptului că, în cel mai rău caz, este necesar să parcurgi toate elementele listei pentru a determina dacă elementul căutat este prezent.

Pentru Set, căutarea folosind contains are o complexitate medie de O(1). Acest lucru se realizează prin utilizarea unui tabel de dispersie pentru stocarea internă a elementelor. În cazul ideal (funcție de dispersie bună și fără coliziuni), căutarea durează timp constant. În cel mai rău caz (multe coliziuni), complexitatea poate fi apropiată de O(n), dar acest lucru este rar în practică.