I need help on this problem. I feel like I'm misunderstanding the question entirely.
Consider a set of n items, and let fi, i = 0, ..., n-1 denote the probability of encountering item i (for instance, if the items represent words of the English language, fi is the frequency at which the i-th word appears in text). Let us assume that the probabilities follow a Geometric distribution, i.e.
fi = c x 2^(-i-1)
a) determine the value of the constant c.
* I think that the sum of all geometric sums is equal to 1, but I can't figure out how this helps me find the constant.
b) What is the expected number of comparisons to find a key (a key I'm assuming is just an element) in a list of size n ordered by frequency (i.e., the most frequent item is first in the list, the second most frequent item is second, etc.
* There must be some way to get a frequency layout like f(most freq) = .33 f2 = .25 f3 = .15 ...... but I'm not sure how to get this.
Any suggestions that could get me on the right path to solving this problem would be greatly appreciated. Thanks for your time!