Why would set creation (and the not x in b inner loop) take O(Nlog(N)) time? I would have thought it would have just required a hash-lookup for each element (O(1)?) being added (and then, a decision to either add the element or not.

Actual times definitely more than O(N) growth.

  a10k = []
  for x in range(10000):
    a10k.append(randint(1,20000))
  %timeit b10k = set(a10k)


   10k elements  = 364 microseconds/loop
  100k elements  = 5 milliseconds/loop
   1mm elements  = 170 milliseconds/loop
  10mm elements  = 2.4 seconds/loop.
 100mm elements  = 34.5 seconds/loop

Presumably the jump from 100k elements to 1mm elements hit that "cache locality" boundary you were referring to.