Self-organizing List - Analysis of Running Times For Access/ Search in A List - Average Case

Average Case

It can be shown that in the average case, the time required to a search on a self-organizing list of size n is

where p(i) is the probability of accessing the ith element in the list, thus also called the access probability. If the access probability of each element is the same (i.e. p(1) = p(2) = p(3) = ... = p(n) = 1/n) then the ordering of the elements is irrelevant and the average time complexity is given by

and T(n) does not depend on the individual access probabilities of the elements in the list in this case. However in the case of searches on lists with non uniform record access probabilities (i.e. those lists in which the probability of accessing one element is different from another), the average time complexity can be reduced drastically by proper positioning of the elements contained in the list.
This is done by pairing smaller i with larger access probabilities so as to reduce the overall average time complexity.
This may be demonstrated as follows:
Given List: A(0.1), B(0.1), C(0.3), D(0.1), E(0.4)
Without rearranging, average search time required is:

Now suppose the nodes are rearranged so that those nodes with highest probability of access are placed closest to the front so that the rearranged list is now:
E(0.4), C(0.3), D(0.1), A(0.1), B(0.1)
Here, average search time is:

Thus the average time required for searching in an organized list is (in this case) around 40% less than the time required to search a randomly arranged list.
This is the concept of the self-organized list in that the average speed of data retrieval is increased by rearranging the nodes according to access frequency.