2

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

user1134991
  • 3,003
  • 2
  • 25
  • 35

1 Answers1

3

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).

Dimitar
  • 4,402
  • 4
  • 31
  • 47
  • 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