analysis we conclude by analyzing the performance of our sortedtablemap implementation summary of the running times for all methods of the sorted map adt (including the traditional map operationsis given in table it should be clear that the len find minand find max methods run in ( timeand that iterating the keys of the table in either direction can be peformed in (ntime the analysis for the various forms of search all depend on the fact that binary search on table with entries runs in (log ntime this claim was originally shown as proposition in section and that analysis clearly applies to our find index method as well we therefore claim an (log nworst-case running time for methods getitem find ltfind gtfind leand find ge each of these makes single call to find indexfollowed by constant number of additional steps to determine the appropriate answer based on the index the analysis of find range is bit more interesting it begins with binary search to find the first item within the range (if anyafter thatit executes loop that takes ( time per iteration to report subsequent values until reaching the end of the range if there are items reported in the rangethe total running time is ( log nin contrast to the efficient search operationsupdate operations for sorted table may take considerable time although binary search can help identify the index at which an update occursboth insertions and deletions requirein the worst casethat linearly many existing elements be shifted in order to maintain the sorted order of the table specificallythe potential call to table insert from within setitem and table pop from within delitem lead to (nworst-case time (see the discussion of corresponding operations of the list class in section in conclusionsorted tables are primarily used in situations where we expect many searches but relatively few updates operation len(mk in [kv del [km find min) find maxm find lt( ) find gt(km find le( ) find ge(km find range(startstopiter( )reversed(mrunning time ( (log no(nworst caseo(log nif existing (nworst case ( (log no( log nwhere items are reported (ntable performance of sorted mapas implemented with sortedtablemap we use to denote the number of items in the map at the time the operation is performed the space requirement is (