(nmn (nmm - ) then linear search for an item in list of size takes on average ( + ** comparisons it is difficult to visualize what these formulae mean in practicebut if we assume the hash table is large but not overloadedi and are both large with mwe can perform taylor approximation for small loading factor / that shows there are + = ( comparisons on average for successful searchi that this has ( complexity for an unsuccessful searchwe need the average list size including the empty slots that will clearly be / land so in an unsuccessful search the average number of comparisons made to decide the item in question is not present will be lwhich is again ( thusneither the successful nor unsuccessful search times depend on the number of keys in the tablebut only on the load factorwhich can be kept low by choosing the size of the hash table to be big enough note also that insertion is done even more speedilysince all we have to do is to insert new element at the front of the appropriate list henceapart from traversalthe complexity class of all operations is constanti ( for traversalwe need to sort the keyswhich can be done in (nlog )as we know from variant would be to make each linked list sortedwhich will speed up finding an itemas well as speed up traversal slightlyalthough this will not put either operation into different complexity class this speed-up would be paid for by making the insertion operation more expensivei take slightly longerbut it will still have constant complexity overallall the time complexities for this approach are clearly very impressive compared to those for sorted arrays or (balancedbinary search trees open addressing the last fundamentally different approach to collision avoidance is called open addressingand that involves finding another open location for any entry which cannot be placed where its hash function points we refer to that position as key' primary position (so in the earlier exampleory and gla have the same primary positionthe easiest strategy for achieving this is to search for open locations by simply decreasing the index considered by one until we find an empty space if this reaches the beginning of the arrayi index we start again at the end this process is called linear probing better approach is to search for an empty location using secondary hash function this process is called double hashing we will now look at both of these approaches in some detail linear probing we now proceed with the earlier example using linear probing we had reached the stagephl gcm ory