• Choose a category
• All
• Classic-Fiction

The runtime complexity of set_difference is O (mn), where m is the size of set1 and n is the size of set2. This is because for each member in set1, the O (n) operation set_is_member is called to determine whether the member is in set2.

set_is_member

The set_is_member operation determines whether a particular member exists in a set (see Example 7.2). This is accomplished by traversing the set using list_next until either a member matching data is found or all members are traversed.

The runtime complexity of set_is_member is O (n), where n is the number of members in the set. This is because, in the worst case, the entire set must be traversed to find the member for which we are searching.

set_is_subset

The set_is_subset operation determines whether one set, set1, is a subset of another set, set2 (see Example 7.2). Since a set that is a subset of another must be the same size or smaller, we begin by comparing sizes. If this test fails, then set1 is not a subset of set2. Otherwise, set1 is traversed using list_next until either a member of set1 that is not in set2 is found or all members are traversed. If we find a member of set1 not in set2, then set1 is not a subset of set2. If we end up traversing all members of set1, then set1 is a subset of set2.

The runtime complexity of set_is_subset is O (mn), where m is the size of set1 and n is the size of set2. This is because for each member in set1, the O (n) operation set_is_member is called to determine whether the member is in set2.

set_is_equal

The set_is_equal operation determines whether one set, set1, is equal to another set, set2 (see Example 7.2). Since two sets that are equal must be the same size, we begin by comparing sizes. If the two sets are not the same size, then they are not equal. If the two sets are the same size, we need only return the result of whether set1 is a subset of set2. This is determined by calling set_is_subset.

The runtime complexity of set_is_equal is O (mn), where m is the size of set1 and n is the size of set2. This is because set_is_subset runs in O (mn) time.

set_size

This macro evaluates to the size of a set (see Example 7.1). It works by accessing the size member of the Set structure.

The runtime complexity of set_size is O (1) because accessing a member of a structure is a simple task that runs in a constant amount of time.

Example 7.2. Set Example: Set Covering

/*****************************************************************************

* *

* -------------------------------- set.c --------------------------------- *

* *

*****************************************************************************/

#include

#include

#include "list.h"

#include "set.h"

/*****************************************************************************

* *

* ------------------------------- set_init ------------------------------- *

* *

*****************************************************************************/

void set_init(Set *set, int (*match)(const void *key1, const void *key2),

void (*destroy)(void *data)) {

/*****************************************************************************

* *

* Initialize the set. *

* *

*****************************************************************************/

list_init(set, destroy);

set->match = match;

return;

}

/*****************************************************************************

* *

* ------------------------------ set_insert ------------------------------ *

* *

*****************************************************************************/

int set_insert(Set *set, const void *data) {

/*****************************************************************************

* *

* Do not allow the insertion of duplicates. *

* *

*****************************************************************************/

if (set_is_member(set, data))

return 1;

/*****************************************************************************