Kā novērtēt meklēšanas efektivitāti pēc atslēgas datu struktūrā Set?

Datu struktūrā Set efektivitāte meklējot elementu pēc atslēgas parasti novērtēta kā O(1) vidēji, ja Set ir realizēts, pamatojoties uz haštabulu (piemēram, HashSet Swift vai NSSet Objective-C). Tas nozīmē, ka meklēšana notiek ļoti ātri, neatkarīgi no kopas lieluma.

Tomēr sliktākajā gadījumā (piemēram, ar daudzām haša kolīzijām), sarežģītība var samazināties līdz O(n). Ja Set ir realizēts, balancēts kokā (piemēram, TreeSet citās valodās), tad meklēšana būs ar sarežģītību O(log n).

Tādējādi meklēšanas efektivitāte ir atkarīga no konkrētās realizācijas, bet standarta hašēto Set gadījumā elementa meklēšana pēc atslēgas parasti ir ļoti ātra un tuvu konstanta laikam.