title: Time complexity of python set operations?
body: <p>What is the the time complexity of each of python's set operations in <a href="http://en.wikipedia.org/wiki/Big_O_notation">Big O</a> notation?</p>
  
  <p>I am using Python's <a href="http://docs.python.org/library/stdtypes.html#set-types-set-frozenset">set type</a> for an operation on a large number of items. I want to know how each operation's performance will be affected by the size of the set. For example, <a href="http://docs.python.org/library/stdtypes.html#set.add">add</a>, and the test for membership:</p>
  
  <pre><code>myset = set()
  myset.add('foo')
  'foo' in myset
  </code></pre>
  
  <p>Googling around hasn't turned up any resources, but it seems reasonable that the time complexity for Python's set implementation would have been carefully considered.</p>
  
  <p>If it exists, a link to something like <a href="http://redis.io/commands/sadd">this</a> would be great. If nothing like this is out there, then perhaps we can work it out?</p>
  
  <p>Extra marks for finding the time complexity of <em>all</em> set operations.</p>