Contrived Example

Bagikan :

Tweet

Assume we have a list of n items:

The a's are ordered by frequency of access

Probability of accessing item : P( ) =

Probability of looking for an item not in the list is

Average cost

U = set of all possible events
P(e) = probability of event e
C(e) = cost of event e


We have:


What is ?

We have:


So

Thus Ave Cost =