What is the Big O complexity for set(l) where l is a list or set(s) where s is a string?
l=[1,2,3,1]
m=set(l) #m=[1,2,3]
s="abca"
t=list(s) #t=['a','b','c']
New-ish to Python and couldn't find the answer anywhere.
Asked
Active
Viewed 624 times
0
Raj
- 3,637
- 8
- 29
- 52
-
well, I googled "python complexity of creating a set" and found this exact duplicate. This question is a nice, fundamental question, that's why it's already been asked here. – Jean-François Fabre Jul 25 '19 at 06:41
-
My bad. I missed the word "creating" – Raj Jul 25 '19 at 07:06
2 Answers
4
Regardless of language, it should be O(n).
Dictionary or Hashset lookup and/or insertion is O(1). Therefore, you just loop over the original list (or string) and insert into the set one by one. This give you O(n).
Edward Aung
- 3,014
- 1
- 12
- 15
3
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).
GOVIND DIXIT
- 1,748
- 10
- 27