INADA Naoki added the comment: > Eric Snow added the comment: > > On Sun, Sep 10, 2017 at 10:27 PM, Serhiy Storchaka > <rep...@bugs.python.org> wrote: >> Note that mixed insertion and deletion is worst-case O(n) in current >> implementation. > > Could you elaborate? Note that every operation of the current > implementation matches the complexity of the Python implementation. >
It means rebuilding hash table to clean up dummy entries. So, even when dict size is not increasing, remove + insert loop has worst case O(n), amortized O(1) complexity. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue31265> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
