What is time complexity of a list to set conversion?

Question

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?

Amphiarthrosis

You could kind of test it... Just time it for increasing n. (I don't know but I guess it should be since insertion in a hash table is most of the time O(1).). – Carnarvon

Thanks I guess I was just too lazy I should get used to using the timer module – Amphiarthrosis

Time complexity questions should be answered in reference to algorithms, not observed timing of operations on your machine. – Poachy

Answer 1

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

Fabiano

In the really worse case when you get a hash collision every time, insertion in a hash table would be O(n) and O(n^2) overall but fortunately this almost never happens. – Carnarvon

Also, if you have very poor memory management or hash binning and a very large list, your performance will not be O(n). – Fabiano

Worst case seems to actually be O(n^2) when collisions happen a lot. Just because it likely won't happen does not mean it changes the worst case. Expected case is O(n). – Gratia

@kiwicomb123. That's noted in the comments. What do you recommend changing in the answer? – Fabiano

when we convert a list to set, it sorts the elements as well, so wouldnt that be O(n.logn) operation? – Ardith

@GopeshKhandelwal. It definitely does not sort the elements. You may have seen a coincidence from an overly short input. Sets are unordered containers. – Fabiano

Answer 2

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

Agentive