Qual è la complessità temporale dell'aggiunta e della rimozione di un elemento in un dizionario in Python?

In Python, il dizionario è implementato su una tabella hash, che garantisce in media una complessità temporale O(1) per le operazioni di aggiunta e rimozione di elementi.

• Aggiunta di un elemento: si calcola l'hash della chiave e l'elemento viene inserito nella cella corrispondente. In media, ciò richiede un tempo costante.
• Rimozione di un elemento: avviene anch'essa tramite l'hash della chiave e richiede in media O(1).

Tuttavia, nel caso peggiore (ad esempio, con molte collisioni), le operazioni possono degradarsi a O(n), dove n è il numero di elementi nel dizionario, ma tali casi sono estremamente rari grazie a una buona implementazione e all'espansione dinamica del dizionario.

Esempio:

my_dict = {}
my_dict['key'] = 'value'  # aggiunta — O(1)
del my_dict['key']          # rimozione — O(1)