0

What is the computational complexity of the following operation:

list1 = [1,2,2,2,3,4,4]
set1 = set(list)
martineau
  • 112,593
  • 23
  • 157
  • 280
Daniel Chepenko
  • 2,087
  • 6
  • 28
  • 50
  • wouldn't that be implementation dependent? (but probably O(N)) – Mitch Wheat Jan 23 '18 at 03:24
  • 1
    Appears this has been answered before: https://stackoverflow.com/questions/34642155/what-is-time-complexity-of-the-python-list-to-set-conversion – Nima Jan 23 '18 at 03:26

1 Answers1

1

It is O(n), where n is the number of elements in the list. set() is essentially iterating over the list and adding each of those elements to a hash table.

cs95
  • 330,695
  • 80
  • 606
  • 657
Surya Avala
  • 149
  • 10