Set insertion is O(n) in this case. An O(1) set insertion refers to constant time regardless of the size of the inserted element, but if you add one element to

Set insertion is O(n) in this case. An O(1) set insertion refers to constant time regardless of the size of the inserted element, but if you add one element to a set, then add a billion elements to the set, the latter will take about a billion times longer.