operation complexities of lists and dictionaries

Steven D'Aprano steve at REMOVETHIScyber.com.au
Thu Mar 30 00:38:12 CEST 2006


On Wed, 29 Mar 2006 09:38:05 -0800, xarnaudx at gmail.com wrote:

> 
> hi,
> i've just a simple question:
> what are the time complexities of inserting / removing / checking if an
> element is present in 1) a list and 2) a dictionary?
> does anybody know?
> thanks

No no no, that's not the way to ask the question, you're hardly likely to
get answers that way.

What you do is, you write in and say "I need a more efficient way of
adding data to a list, because adding data to a list is O(n**2) and that's
too slow. Also, how do I implement hash tables in Python, because I need
O(1) searching?"

That way you'll have dozens, maybe hundreds of replies from people
explaining that adding data to Python lists is O(log n) amortized, and
that dictionaries are hash tables.

*wink*

-- 
Steven.
 



More information about the Python-list mailing list