I don't know about the implementation, but as an exercise, the set union is O(N) w.r.t. len(s)+len(t), and stays the same regardless of the degree of coincidence of s and t.

Check TimeComplexity for more details

================

import timeit

# Time with varying length of s and t

setup = """
from random import random
s = set(random() for i in xrange(%d))
t = set(random() for i in xrange(%d))
"""

cmd = "u = s|t"

for len_s in xrange(1,101,10):
    for len_t in xrange(1,101,10):
        ans = timeit.Timer(cmd, setup=setup % (len_s, len_t)).timeit(200)
        print '%3d' % (len_s+len_t), '%6.4f' % (ans*1e4/(len_s+len_t))

# Time with varying % of elements in both sets

setup = """
from random import random
n = 2000
k = int(n * %4.3f)
u = set(random() for i in xrange(k))
s = set(random() for i in xrange(n-k)) | u
t = set(random() for i in xrange(n-k)) | u
"""

cmd = """v = s|t"""

for i in xrange(0,101,5):
    k = 0.01*i
    ans = timeit.Timer(cmd, setup=setup % k).timeit(100)
    print '%3.2f' % k, '%6.1f' % (ans*1e4)