Tcl dict unset order of complexity

Question

If I am doing dict unset, what is the average order of complexity?
I am really crossing my fingers for O(1).
Thanks

score 2 · Accepted Answer · answered Jan 29 '16 at 14:46

2

Tcl's dict is internally implemented as a hashtable. The command:

dict unset removes a key and its associated value from a dictionary of dictionaries.

Therefore it is in worst case O(n). With an average of O(1).

answered Jan 29 '16 at 14:46

Dimitar

1

Thanks. That is what i have guessed and hoped for, but could not be certain of. – user1134991 Jan 29 '16 at 14:59
Possibly of interest to readers of this answer: [Hash table runtime complexity (insert, search and delete)](http://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete) – dfrib Jan 30 '16 at 02:34
1

You'd only get O(n) with very carefully crafted dictionaries. You can use `dict info` to analyse the time to look up a key and its entry. (There is, of course, a constant amount of work to delete the entry once it has been found.) – Donal Fellows Jan 31 '16 at 08:44

1 Answers1