➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author methane
Recipients arigo, aronacher, eric.snow, methane, rhettinger, serhiy.storchaka
Date 2017-09-12.07:27:13
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <CAEfz+Tzgi-mno2+LptTV6Zm_KoNR5kJLdFWEgZ4OoPEtF-AeWQ@mail.gmail.com>
In-reply-to <CALFfu7CgMX7orT=qD41_EykGgNhDMftDqvgVNcK13K9KsJz_Gw@mail.gmail.com>
Content 
> Eric Snow added the comment:
>
> On Sun, Sep 10, 2017 at 10:27 PM, Serhiy Storchaka
> <report@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.
History
Date User Action Args
2017-09-12 07:27:13methanesetrecipients: + methane, arigo, rhettinger, aronacher, eric.snow, serhiy.storchaka
2017-09-12 07:27:13methanelinkissue31265 messages
2017-09-12 07:27:13methanecreate