What is time complexity of a list to set conversion?

python list hash set time-complexity
lxuechen picture lxuechen · Jan 6, 2016 · Viewed 27.5k times · Source

I've noticed the table of the time complexity of set operations on the python official website. But i just wanna ask what's the time complexity of converting a list to a set, for instance,

l = [1, 2, 3, 4, 5]
s = set(l)

I kind of know that this is actually a hash table, but how exactly does it work? Is it O(n) then?

Answer

Mad Physicist picture Mad Physicist · Jan 6, 2016

Yes. Iterating over a list is O(n) and adding each element to the hash set is O(1), so the total operation is O(n).

Related questions

Finding the index of an item in a list

Given a list ["foo", "bar", "baz"] and an item in the list "bar", how do I get its index (1) in Python?

Read More
How do I get the number of elements in a list?

Consider the following: items = [] items.append("apple") items.append("orange") items.append("banana") # FAKE METHOD: items.amount() # Should return 3 How do I get the number of elements in the list items?

Read More
How do I check if a list is empty?

For example, if passed the following: a = [] How do I check to see if a is empty?

Read More