I didn't claim it wasn't O(1). I just said that for sets to automatically be sorted like the parent comment claimed, it would have to be O(logn) insertion since that's the fastest you can insert into a sorted data structure. Obviously sets are not sorted, and thus are able to maintain O(1) insertion.