Quanto tempo impiega la ricerca (ad esempio, utilizzando il metodo contains) nelle collezioni List e Set?

Per List, la ricerca con contains ha una complessità computazionale di O(n), dove n è il numero di elementi nella lista. Ciò è dovuto al fatto che, nel peggiore dei casi, è necessario scorrere tutti gli elementi della lista per determinare se l'elemento cercato è presente.

Per Set, la ricerca con contains ha una complessità media di O(1). Questo si ottiene utilizzando una tabella hash per la memorizzazione interna degli elementi. Nel caso ideale (buona funzione hash e assenza di collisioni), la ricerca richiede un tempo costante. Nel caso peggiore (molte collisioni), la complessità può avvicinarsi a O(n), ma questo è raro nella pratica.