95

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?

martineau
  • 119,623
  • 25
  • 170
  • 301
lxuechen
  • 1,129
  • 1
  • 9
  • 9

2 Answers2

107

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

Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
  • 23
    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. – NoDataDumpNoContribution Jan 06 '16 at 21:50
  • Also, if you have very poor memory management or hash binning and a very large list, your performance will not be O(n). – Mad Physicist Jan 07 '16 at 00:38
  • 1
    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). – kiwicomb123 Sep 23 '22 at 13:19
  • @kiwicomb123. That's noted in the comments. What do you recommend changing in the answer? – Mad Physicist Sep 23 '22 at 13:39
  • when we convert a list to set, it sorts the elements as well, so wouldnt that be O(n.logn) operation? – Gopesh Khandelwal Jan 02 '23 at 09:41
  • 1
    @GopeshKhandelwal. It definitely does not sort the elements. You may have seen a coincidence from an overly short input. Sets are unordered containers. – Mad Physicist Jan 02 '23 at 16:32
3

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

Aven Desta
  • 2,114
  • 12
  • 27