thuswe have mlogn which implies that binary search runs in (logntime there is simple variation of binary search that performs findall(kin time (logn )where is the number of entries in the iterator returned the details are left as an exercise ( - thuswe can use an ordered search table to perform fast dictionary searchesbut using such table for lots of dictionary updates would take considerable amount of time for this reasonthe primary applications for search tables are in situations where we expect few updates to the dictionary but many searches such situation could arisefor examplein an ordered list of english words we use to order entries in an encyclopedia or help file comparing dictionary implementations table compares the running times of the methods of dictionary realized by either an unordered lista hash tableor an ordered search table note that an unordered list allows for fast insertions but slow searches and removalswhereas search table allows for fast searches but slow insertions and removals incidentallyalthough we don' explicitly discuss itwe note that sorted list implemented with doubly linked list would be slow in performing almost all the dictionary operations (see exercise - table comparison of the running times of the methods of dictionary realized by means of an unordered lista hash tableor an ordered search table we let denote the number of entries in the dictionaryn denote the capacity of the bucket array in the hash table implementationsand denote the size of collection returned by operation findall the space requirement of all the implementations is ( )assuming that the arrays supporting the hash table and search table implementations are maintained such that their capacity is proportional to the number of entries in the dictionary