sets and maps operation union intersection complexity (no(nusage update(ts intersection_update(tset difference symmetric difference add remove (no(no( ( difference_update(ts symmetric_difference _update(ts add(es remove(ediscard ( discard(epop clear ( ( pop( clear(description adds the contents of to updates to contain only the intersection of the elements from and subtracts from the elements of updates with the symmetric difference of and add the element to the set remove the element from the set this raises keyerror if does not exist in remove the element if it exists in and ignore it otherwise remove an arbitrary element of remove all the elements of leaving the set empty fig mutable set operations the computational complexities presented above are surprisinghow can set membership be tested in ( timefrom what has been presented so farit should take (ntime to test set membership after allwe would have to look at all the elements in the setor at least half on averageto know if an item was in the set how can the union of two sets be computed in (ntime if we are to insure there are no duplicates in the setit would seem that the union of two sets would take ( time to compute unless the set could be sorted in some way but sorting elements of set is not always possible since not all elements of sets have an ordering hashing if it is possible to implement set membership test in ( timethen we can implement the other operations above with the complexities we have indicated without ( membership testtaking the union of two sets would take lot longer as indicated above testing set membership in ( time is accomplished using hashing hashing is an extremely important concept in computer science and is related to random access in computer as we saw back in chap accessing any location within list can be accomplished in ( time this is the principle of random access randomly accessible list means any location within the list can be accessed in ( time to access location in list we need the index of the location we wish to access the index serves as the address of an item in the list once we have stored an item in the listwe must remember its index if we wish to retrieve it in ( time without the index we would have to search for the item in the list which would take (ntimenot ( time soif we wanted to implement set where we could test membership in ( time we might think of storing the items of the set in list we would somehow have to remember the index where each item was stored to find it again in ( time this seems improbable at first howeverwhat if the item could be used to figure out its addressthis is the insight that led to hashing each object in the computer must this copy belongs to 'acha