What is time complexity of a list to set conversion?
42,540
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)
.
Author by
lxuechen
Updated on July 05, 2022Comments
-
lxuechen almost 2 years
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?
-
Trilarion over 8 yearsYou 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).).
-
lxuechen over 8 yearsThanks I guess I was just too lazy I should get used to using the timer module
-
Jacob Lee over 4 yearsTime complexity questions should be answered in reference to algorithms, not observed timing of operations on your machine.
-
-
Trilarion over 8 yearsIn 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.
-
Mad Physicist over 8 yearsAlso, if you have very poor memory management or hash binning and a very large list, your performance will not be O(n).