**Q:** Instead of
implementing *set_is_subset* as shown, how could we
use other set operations to determine if one set,
*S _{1} *, is a subset of
another set,

**A:** In set notation, if
*S* _{1} ∩ *S*
_{2} = *S*
_{1}, then *S*
_{1} ⊂ *S*
_{2}. Therefore, we could use a combination of the
*set_intersection* and
*set_is_equal* operations . Whether we implement this operation as shown or use
*set_intersection* and
*set_is_equal*, its runtime complexity is
*O* (*mn*), where
*m* is the size of *S*
_{1} and *n* is the size of
*S* _{2}. However, in the case
of calling *set_intersection* and
*set_is_equal*, the running time is actually closer
to *T* (*m*,*
n*) = 2*mn* because both
*set_intersection* and
*set_is_equal* run in *T
*(*m*,* n*) =
*mn* times some constant. Compare this with the
operation *set_is_subset*, which runs closer to
*T* (*m*,
*n*) = *mn*. Although the
complexities of the two methods are the same, calling
*set_intersection* and
*set_is_equal* requires approximately double the
time in practice.

**Q:** Instead of implementing
*set_is_equal* as shown, how could we use other set
operations to determine if one set,
*S _{1} *, is equal to another
set,

**A:** In set notation, if
*S* _{1} −
*S* _{2} = ∅ and *S*
_{2} − *S*
_{1} = ∅, then *S*
_{1} = *S*
_{2}. Therefore, we could implement this, albeit
less efficiently, using two calls to
*set_difference* and two calls to
*set_size*.

**Q:** Instead of implementing
*set_intersection* as shown, how could we use the
*set_difference* operation to compute the
intersection of two sets, *S _{1}
* and

**A:** In set notation,
*S* _{1} ∩ *S*
_{2} = *S*
_{1}

Start Free Trial

No credit card required