Колко време отнема търсенето (например, с метода contains) в колекциите List и Set?

За List търсенето с използване на contains има изчислителна сложност O(n), където n е броят на елементите в списъка. Това се дължи на факта, че в най-лошия случай е необходимо да се прегледат всички елементи на списъка, за да се определи наличието на търсения елемент.

За Set, търсенето с използване на contains има средна изчислителна сложност O(1). Това се постига чрез използване на хеш таблица за вътрешното съхранение на елементите. В идеалния случай (добра хеш функция и липса на колизии), търсенето отнема постоянен време. В най-лошия случай (много колизии), сложността може да се приближи до O(n), но това е рядко на практика.