Πόσο διαρκεί η αναζήτηση (για παράδειγμα, με τη μέθοδο contains) στις συλλογές List και Set;

Για το List, η αναζήτηση με χρήση contains έχει υπολογιστική πολυπλοκότητα O(n), όπου n είναι ο αριθμός των στοιχείων στη λίστα. Αυτό οφείλεται στο γεγονός ότι, στην χειρότερη περίπτωση, απαιτείται να διασχίσετε όλα τα στοιχεία της λίστας για να προσδιορίσετε αν το ζητούμενο στοιχείο υπάρχει.

Για το Set, η αναζήτηση με χρήση contains έχει μέση υπολογιστική πολυπλοκότητα O(1). Αυτό επιτυγχάνεται με τη χρήση ενός πίνακα κατακερματισμού για την εσωτερική αποθήκευση των στοιχείων. Στην ιδανική περίπτωση (καλή συνάρτηση κατακερματισμού και χωρίς συγκρούσεις), η αναζήτηση διαρκεί σταθερό χρόνο. Στην χειρότερη περίπτωση (πολλές συγκρούσεις), η πολυπλοκότητα μπορεί να προσεγγίσει το O(n), αλλά αυτό είναι σπάνιο στην πράξη.