python - 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?

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
Thanks I guess I was just too lazy I should get used to using the timer module — lxuechen
Time complexity questions should be answered in reference to algorithms, not observed timing of operations on your machine. — Jacob Lee

Mad Physicist Mad Physicist · Accepted Answer · 2016-01-06T20:31:37

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

python - What is time complexity of a list to set conversion?

1 Answers