Run this on Python 3 or use xrange instead of range on Python 2 and you get N space instead of 2N anyway :)

Also, the average case for set membership testing is O(1), so the average case runtime would actually be O(N).

https://wiki.python.org/moin/TimeComplexity#set