minte9
LearnRemember   ALGORITHMS





PVM / Python / Data Structures / Sets

1. Inserting Sets

In terms of time compexity, the only difference between lists and sets is at insertion. Reading O(1), Searching O(n), Deleting O(n), Inserting O(1) A set stores unique, unordered elements (it rejects duplicates). Insertion is (on average) O(1) thanks to hashing. As analogy, think of a guest list where each name can appear only once. Adding a new name is instant, trying to add an existing name changes nothing. Inserting mutates the input set. There is no need for duplicate checks. Python sets already handle duplicates in O(1). 
 py
# Inserting into a set O(1)
fruits = {'apples', 'bananas', 'oranges'}

# Custom insert function
def add_item(items, value):
    steps = 0

    # Duplicate check
    # for item in items:
    #     steps += 1
    #     if item == value:
    #         return -1

    # Insert (set chooses the storage location, order is arbitrary)
    items.add(value)

    steps += 1
    return steps

steps = add_item(fruits, 'kiwi')
print(fruits, steps)

"""
    {'bananas', 'apples', 'kiwi', 'oranges'} 1
"""




References: