Mekkora az időbeli komplexitása az adathalmaz elejére történő elem beszúrásának?

Az adathalmazba történő elem beszúrásának időbeli összetettsége attól függ, hogy milyen adatszerkezetet használunk az adathalmaz tárolására.

• Ha az adathalmaz láncolt listaként van megvalósítva (például egysoros láncolt lista), akkor a beszúrás az eleje O(1) összetettségű, mivel elegendő az új elem mutatóját módosítani.
• Ha az adathalmaz tömbként vagy dinamikus tömbként (például ArrayList) van megvalósítva, akkor az elejére történő beszúrás minden elem eltolását igényli, ami O(n) összetettséget eredményez.
• A szokásos adatszerkezetekben (például Swift HashSet vagy iOS Set) nincs "kezdet" fogalom, mivel az adathalmaz nem rendezett. Az elem beszúrása általában amortizált O(1) időben történik.

Tehát, ha kifejezetten egy halmazról (Set) beszélünk, akkor az elem beszúrásának nincs "kezdet" fogalma, és O(1) idő alatt történik. Rendezett kollekció esetén a beszúrás az elejére lehet O(1) vagy O(n), az implementációtól függően.