In computer science, it often occurs that items must be located within a list. How the items are stored in the list affects how long it takes to locate the items.
a) Suppose n items are stored in random order. To find a requested item, the items are searched sequentially until that item is found (assuming the requested item is on the list, of course). Let X be the number of items in the list that must be accessed (looked at) until the requested item is found. What is E(X)?
b) Suppose that 255 items are stored in a list in order and that we can access any element in the list. Now a binary search can be used to locate the requested item. We can look in the middle location, and if the item is not there, we will know if it is to the left or the right, etc. Now what is the expected number of items looked at? (Compare this with the result from part a) when n = 255.)