Mekkora az időbeli komplexitása egy elem beszúrásának egy halmaz adatstruktúrában?

Halmaz (Set) adatszerkezetben általában nincs "középre való beszúrás" fogalom, mivel a halmazok nem rendezettek és nincsenek indexek. Egy elem beszúrása a halmazba általában amortizált időben O(1), ha hash-táblát használunk, vagy O(log n), ha a halmaz egy kiegyensúlyozott fára van alapozva.

Ha olyan adatszerkezetet veszünk figyelembe, ahol a sorrend fontos (például tömb vagy lista), akkor a tömb közepébe való beszúrás elemek eltolását igényli, és időbeli komplexitása O(n). Listákban (például láncolt listák) a pozíció keresése után a beszúrás O(1), de a pozíció keresése O(n).

Összefoglalva, egy halmazba való beszúrás O(1) vagy O(log n), a megvalósítástól függően, és a "közép" fogalom nem alkalmazható.