CODEWITHSUNDEEP
pythonlisthashsettime-complexity
lxuechen
lxuechen

Reputation: 1199

What is time complexity of a list to set conversion?

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?

Upvotes: 102

Views: 61669

Answers (2)

Aven Desta
Aven Desta

Reputation: 2443

I was asked the same question in my last interview and didn't get it right. As Trilarion commented in the first solution, the worst-case complexity is O(n^2). Iterating through the list will need O(n), but you can not just add each element to the hash table (sets are implemented using hashtables). In the worst case, our hash function will hash each element to the same value, thus adding each element to the hash set is not O(1). In such a case, we need to add each element to a linked list - (note that hash sets have a linked list in case of collision). When adding to the linked list we need to make sure that the element doesn't already exist (as a Set by definition doesn't have duplicates). To do that we need to iterate through the same linked list for each element, which takes a total of n*(n-1)/2 = O(n^2).

Upvotes: 8

Mad Physicist
Mad Physicist

Reputation: 114330

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).

Upvotes: 112

Related Questions