100

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?

Improve this question
3
  • 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).).
    – NoDataDumpNoContribution
    Commented Jan 6, 2016 at 20:52
  • Thanks I guess I was just too lazy I should get used to using the timer module
    – lxuechen
    Commented Jan 6, 2016 at 21:07
  • 7
    Time complexity questions should be answered in reference to algorithms, not observed timing of operations on your machine.
    – Jacob Lee
    Commented Sep 19, 2019 at 18:04

2 Answers 2

Reset to default
110

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

Improve this answer
6
  • 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
    Commented Jan 6, 2016 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
    Commented Jan 7, 2016 at 0: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
    Commented Sep 23, 2022 at 13:19
  • @kiwicomb123. That's noted in the comments. What do you recommend changing in the answer?
    – Mad Physicist
    Commented Sep 23, 2022 at 13:39
  • 2
    @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
    Commented Jan 2, 2023 at 16:32
6

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

Improve this answer
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.