chap searching self-organizing lists while lists are most commonly ordered by key valuethis is not the only viable option another approach to organizing lists to speed search is to order the records by expected frequency of access while the benefits might not be as great as when organized by key valuethe cost to organize by frequency of access is much cheaperand thus is of use in some situations assume that we knowfor each key ki the probability pi that the record with key ki will be requested assume also that the list is ordered so that the most frequently requested record is firstthen the next most frequently requested recordand so on search in the list will be done sequentiallybeginning with the first position over the course of many searchesthe expected number of comparisons required for one search is npn in other wordsthe cost to access the first record is one (because one key value is looked at)and the probability of this occurring is the cost to access the second record is two (because we must look at the first and the second recordskey values)with probability and so on for recordsassuming that all searches are for records that actually existthe probabilities through pn must sum to one certain probability distributions give easily computed results example calculate the expected cost to search list when each record has equal chance of being accessed (the classic sequential search through an unsorted listsetting pi / yields cn / ( )/ = this result matches our expectation that half the records will be accessed on average by normal sequential search if the records truly have equal access probabilitiesthen ordering records by frequency yields no benefit we saw in section the more general case where we must consider the probability (labeled that the search key does not match that for any record in the array in that casein accordance with our general formulawe get ( thusn+ < <ndepending on the value of