Ile czasu zajmuje wyszukiwanie (np. za pomocą metody contains) w kolekcjach List i Set?

Dla List, wyszukiwanie za pomocą contains ma złożoność obliczeniową O(n), gdzie n to liczba elementów na liście. Wynika to z faktu, że w najgorszym przypadku konieczne jest przeszukanie wszystkich elementów listy, aby ustalić, czy poszukiwany element jest obecny.

Dla Set, wyszukiwanie za pomocą contains ma średnią złożoność O(1). Osiąga się to dzięki użyciu tablicy haszującej do wewnętrznego przechowywania elementów. W idealnym przypadku (dobra funkcja haszująca i brak kolizji), wyszukiwanie zajmuje czas stały. W najgorszym przypadku (wiele kolizji), złożoność może zbliżać się do O(n), ale jest to rzadkie w praktyce.