Quanto tempo leva a pesquisa (por exemplo, usando o método contains) em coleções List e Set?

Para List, a pesquisa usando contains tem uma complexidade computacional de O(n), onde n é o número de elementos na lista. Isto deve-se ao facto de que, no pior caso, é necessário percorrer todos os elementos da lista para determinar se o elemento procurado está presente.

Para Set, a pesquisa usando contains tem uma complexidade média de O(1). Isto é conseguido através do uso de uma tabela de hash para o armazenamento interno dos elementos. No caso ideal (boa função de hash e ausência de colisões), a pesquisa leva tempo constante. No pior caso (muitas colisões), a complexidade pode aproximar-se de O(n), mas isto é raro na prática.