Wat is de complexiteit van het controleren of een element in een set aanwezig is in het slechtste geval, wanneer alle elementen dezelfde hash hebben?

In het slechtste geval, wanneer alle elementen in een set dezelfde hash hebben, degradeert de datastructuur, meestal geïmplementeerd als een hash-tabel, naar een gekoppelde lijst. Dit gebeurt omdat alle elementen in één bak (bucket) terechtkomen.

In dat geval vereist het controleren of een element aanwezig is, het doorlopen van alle elementen in die bak, wat een complexiteit van O(n) oplevert, waarbij n het aantal elementen in de set is.

Dus, in het slechtste geval, is het zoeken naar een element in een set een lineair zoekproces in de lijst, en geen constante tijd zoals in het gemiddelde geval.