Removing duplicates from a list by set and for loop

Question

Which one is faster operation, How to find complexity?

1:
newList = list(set(itemList))   # what is the time complexity?  
  
2:
for i in itemList:              # O(n)  
  if i not in tempList:  
   tempList.append(i)

Also, I would like to know where I can find detail info of internal working on the derived data structure of python. I am sure that there must be some internal traversal, searching or hashing concept.

I tried this:

import time

itemList = [1,2,3,1,2,3,1,2,3,1,1]*1000000

def removeDups(itemList):
    newList = list(set(itemList))   # what is the time complexity?
    return newList

def removeDups2(itemList):
    newList = []
    for i in itemList:              # O(n)
       if i not in newList:
          newList.append(i)
    return newList 

start_time = time.time()
removeDups(itemList)
print("--- %s seconds ---" % (time.time() - start_time))

start_time = time.time()
removeDups2(itemList)
print("--- %s seconds ---" % (time.time() - start_time))

and found that:
removeDups took --- 0.07812380790710449 seconds
removeDups2 took --- 0.23437118530273438 seconds

No Doubt, Set() is faster but how?

Sets are faster because sets have been implemented using hash tables. So basically Python does not have to search the full set, which means that the time complexity in average is O(1). https://stackoverflow.com/questions/8929284/what-makes-sets-faster-than-lists#:~:text=Generally%20the%20lists%20are%20faster,average%20is%20O(1). — Ajay K, Dec 02 '22 at 13:17
Because of `not in newList`, the function `removeDups2` has a O(n²) time complexity. — trincot, Dec 02 '22 at 13:45
@AjayK : Thanks for your answer, this clarifies half of my understanding, however, the question also goes in the direction where a list is first converted into set and somehow i think each element must have been traversed to put into hash table where the duplicates have been removed. but then again a set is converted into list. ```list(set(itemList))``` How could this be answered? — Raj Sharma, Dec 02 '22 at 13:56

Removing duplicates from a list by set and for loop

0 Answers0