David Martínez MartíNov 30, 2022
@nosherwan @xblasco we are still discussing... It's not an easy topic.
Show threadDavid Martínez MartíNov 30, 2022

@nosherwan @xblasco This article for #Python #dicts is interesting: https://tenthousandmeters.com/blog/python-behind-the-scenes-10-how-python-dictionaries-work/

For one, it reiterates the time complexity as O(1), but then you can see the graph where it doesn't follow theory when benchmarked.

The article explains why. CPU Caches.

But the underlying question is, should be considered O(1) if in practice doesn't follow it?

Python behind the scenes #10: how Python dictionaries work

Python dictionaries are an extremely important part of Python. Of course they are important because programmers use them a lot, but that's not the...

Show threadNed BatchelderNov 30, 2022
@deavid @nosherwan @xblasco Real timing graphs will never follow the mathematical theory. Looks like your graph is essentially flat (between 400ns and 500ns from 500k to 50M items), so yes: O(1)
Show threadDavid Martínez Martí
@nedbat @nosherwan @xblasco totally agree. However I fail to find where is stated that Big-O is theory, only formal, and not practice. I was hoping for wikipedia, but if it's there I cannot find or understand it
Nov 30, 2022 at 4:24pmWeb