Qual è la complessità temporale dell'inserimento di un elemento nel mezzo di una struttura dati di insieme?

Nella struttura dati dei set (Set), di solito non esiste il concetto di "inserimento nel mezzo", poiché i set non sono ordinati e non hanno indici. L'inserimento di un elemento in un set avviene generalmente in tempo amortizzato O(1), se si utilizza una tabella hash, o O(log n), se il set è implementato su un albero bilanciato.

Se si considera una struttura dati in cui l'ordine è importante (ad esempio, un array o una lista), l'inserimento nel mezzo di un array richiede lo spostamento degli elementi e ha una complessità temporale O(n). Nelle liste (ad esempio, liste concatenate), l'inserimento nel mezzo dopo aver trovato la posizione è O(1), ma la ricerca della posizione è O(n).

In sintesi, per un set, l'inserimento è O(1) o O(log n), a seconda dell'implementazione, e il concetto di "mezz'" non è applicabile.