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):

# 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):

TimeComplexity (SetCode) (last edited 2008-11-15 14:01:26 by localhost)

Unable to edit the page? See the FrontPage for instructions.