subtract( )replace with the difference of and bthat isexecute - simple set implementation one of the simplest ways of implementing set is to store its elements in an ordered sequence this implementation is included in several software libraries for generic data structuresfor example thereforelet us consider implementing the set adt with an ordered sequence (we consider other implementations in several exercisesany consistent total order relation among the elements of the set can be usedprovided the same order is used for all the sets we implement each of the three fundamental set operations using generic version of the merge algorithm that takesas inputtwo sorted sequences representing the input setsand constructs sequence representing the output setbe it the unionintersectionor subtraction of the input sets incidentallywe have defined these operations so that they modify the contents of the set involved alternativelywe could have defined these methods so that they do not modify but return new set instead the generic merge algorithm iteratively examines and compares the current elements and of the input sequence and brespectivelyand finds out whether thenbased on the outcome of this comparisonit determines whether it should copy one of the elements and to the end of the output sequence this determination is made based on the particular operation we are performingbe it unionintersectionor subtraction for examplein union operationwe proceed as followsif bwe copy to the end of and advance to the next element of if bwe copy to the end of and advance to the next elements of and if bwe copy to the end of and advance to the next element of performance of generic merging let us analyze the running time of generic merging at each iterationwe compare two elements of the input sequences and bpossibly copy one element to the output sequenceand advance the current element of abor both assuming that comparing and copying elements takes ( timethe total running time is ( )where is the size of and is the size of bthat is