80

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
  • 112,593
  • 23
  • 157
  • 280
lxuechen
  • 979
  • 1
  • 8
  • 9
  • 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).). – Trilarion Jan 06 '16 at 20:52
  • Thanks I guess I was just too lazy I should get used to using the timer module – lxuechen Jan 06 '16 at 21:07
  • 5
    Time complexity questions should be answered in reference to algorithms, not observed timing of operations on your machine. – Jacob Lee Sep 19 '19 at 18:04

1 Answers1

91

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
  • 95,415
  • 23
  • 151
  • 231
  • 17
    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. – Trilarion 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