5.9 Evaluating the Set Implementation

We can use complexity analysis to determine the efficiency of the Set ADT operations as implemented in the previous section. For convenience, the relevant portions of that implementation are shown again in the program listing below. The evaluation is quite simple since the ADT was implemented using the list and we just evaluated the methods for that structure. Table 5.9.1 provides a summary of the worst case time-complexities for the set operations implemented earlier in the chapter.

Program Listing

Listing of the Set ADT implementation.

Program: linearset.py # Implementation of the Set ADT container using a Python list. class Set :      # Creates an empty set instance.   def __init__(self) :     self._theElements = list()        # Returns the number of items in the set.   def __len__(self) :     return len(self._theElements)        # Returns True if the set is empty and False otherwise.   def isEmpty(self) :     return len(self._theElements) == 0        # Determines if an element is in the set.   def __contains__(self, element) :     return element in self._theElements          # Adds a new unique element to the set.   def add(self, element) :                       if element not in self :       self._theElements.append( element )              # Removes an element from the set.   def remove(self, element) :     assert element in self, "The element must be in the set."     self._theElements.remove( item )        # Removes all of the elements from the set.   def clear(self) :     ......        # Determines if two sets are equal.   def __eq__(self, setB) :                       if len(self) != len(setB) :       return False     else :       return self.isSubsetOf(setB)                  # Determines if this set is a subset of setB.   def isSubsetOf(self, setB) :                   for element in self._theElements :       if element not in setB :         return False     return True                                      # Creates a new set from the union of this set and setB.   def union(self, setB) :                         newSet = Set()       newSet._theElements.extend(self._theElements)     for element in setB._theElements :       if element not in self :         newSet._theElements.append(element)     return newSet                                    # Creates a new set from the intersection: self set and setB.   def interset( self, setB ):     ......        # Creates a new set from the difference: self set and setB.   def difference( self, setB ):     ......        # Returns an iterator for traversing the list of items.   def __iter__( self ):     return iter(self._theElements)

Simple Operations

set contains
set add

worst-case: $\text{O}\left(n\right)$

Evaluating the constructor and length operation is straightforward as they simply call the corresponding list operation. The __contains__ method, which determines if an element is contained in the set, uses the in operator to perform a linear search over the elements stored in the underlying list. The search operation, which requires $\text{O}\left(n\right)$, will be presented in the next chapter and we postpone its analysis until that time. The add method also requires $\text{O}\left(n\right)$ time in the worst case since it uses the in operator to determine if the element is unique and the append method to add the unique item to the underlying list, both of which require linear time in the worst case.

Operations of Two Sets

The remaining methods of the Set class involve the use of two sets, which we label $\text{A}$ and $\text{B}$, where $\text{A}$ is the self set and $\text{B}$ is the argument passed to the given method. To simplify the analysis, we assume each set contains $\text{n}$ elements. A more complete analysis would involve the use of two variables, one for the size of each set. But the analysis of this more specific case is sufficient for our purposes.

set subset
set equals

worst-case: $\text{O}\left(n^2\right)$

The isSubsetOf method determines if $\text{A}$ is a subset of $\text{B}$. It iterates over the $n$ elements of set $\text{A}$, during which the in operator is used to determine if the given element is a member of set $\text{B}$. Since there are $n$ repetitions of the loop and each use of the in operator requires $\text{O}\left(n\right)$ time, the isSubsetOf method has a quadratic run time of $\text{O}\left(n^2\right)$. The set equality operation is also $\text{O}\left(n^2\right)$ since it calls isSubsetOf after determining the two sets are of equal size.

Set Union Operation

The set union operation creates a new set, $\text{C}$, that contains all of the unique elements from both sets $\text{A}$ and $\text{B}$. It requires three steps.

• The first step creates the new set $\text{C}$, which can be done in constant time.
• The second step fills set $\text{C}$ with the elements from set $\text{A}$, which requires $\text{O}\left(n\right)$ time since the extend list method is used to add the elements to set $\text{C}$.
• The last step iterates over the elements of set $\text{B}$ during which the in operator is used to determine if the given element is a member of set $\text{A}$. If the element is not a member of set $\text{A}$, it's added to set $\text{C}$ by applying the append list method. We know from earlier the linear search performed by the in operator requires $\text{O}\left(n\right)$ time and we can use the $\text{O}\left(1\right)$ amortized cost of the append method since it is applied in sequence. Given that the loop is performed $n$ times and each iteration requires $n+1$ time, this step requires $\text{O}\left(n^2\right)$ time.

set union

worst-case: $\text{O}\left(n^2\right)$

Combining the times for the three steps yields a worst case time of $\text{O}\left(n^2\right)$.