¿En qué tiempo se realiza la búsqueda (por ejemplo, usando el método contains) en colecciones List y Set?

Para List, la búsqueda usando contains tiene una complejidad computacional de O(n), donde n es la cantidad de elementos en la lista. Esto se debe a que, en el peor de los casos, es necesario recorrer todos los elementos de la lista para determinar si el elemento buscado está presente.

Para Set, la búsqueda usando contains tiene una complejidad computacional promedio de O(1). Esto se logra mediante el uso de una tabla hash para el almacenamiento interno de los elementos. En el caso ideal (una buena función hash y sin colisiones), la búsqueda toma tiempo constante. En el peor de los casos (muchas colisiones), la complejidad puede acercarse a O(n), pero esto es raro en la práctica.