mapshash tablesand skip lists maintaining maxima set with sorted map we can store the set of maxima pairs in sorted mapmso that the cost is the key field and performance (speedis the value field we can then implement operations add(cp)which adds new cost-performance pair (cp)and best( )which returns the best pair with cost at most cas shown in code fragment class costperformancedatabase """maintain database of maximal (cost,performancepairs "" def init (self) """create an empty database ""or more efficient sorted map self sortedtablemap def best(selfc) """return (cost,performancepair with largest cost not exceeding return none if there is no such pair "" return self find le( def add(selfcp) """add new entry with cost and performance "" determine if ( ,pis dominated by an existing pair other is at least as cheap as other self find le( if other is not none and other[ >pif its performance is as good return ( ,pis dominatedso ignore elseadd ( ,pto database self [cp and now remove any pairs that are dominated by ( ,pother more expensive than other self find gt( while other is not none and other[ < del self [other[ ] other self find gt(ccode fragment an implementation of class maintaining set of maxima cost-performance pairs using sorted map unfortunatelyif we implement using the sortedtablemapthe add behavior has (nworst-case running time ifon the other handwe implement using skip listwhich we next describewe can perform best(cqueries in (log nexpected time and add(cpupdates in (( rlog nexpected timewhere is the number of points removed