# Optimal Word Guessing Algorithm in $O(n \log n)$

Say that your friend picks a word $$(w_1, w_2,\dots,w_n)$$ according to a known probability distribution $$(p_1,p_2,\dots,p_n)$$. You ask yes or no questions until you are certain which word has been chosen. For example, you can eliminate a subset $$S$$ with the question "Is the word in $$S$$?" The cost of the guessing strategy is the expected number of queries it takes to find the right word. Let an optimal strategy be one that minimizes cost. Design an $$O(n \log n)$$ algorithm to determine the cost of the optimal strategy.

I'm really confused about this question. I know one strategy would be to ask "is it {word i}" in linear time, but apparently thats nonoptimal? Another thought I had would be to sort the probabilities greatest to least as $$(w_a, w_b, w_c,\dots)$$ and ask "is it {word a,b...}" until you get the right answer. But I think that could be worst case $$O(n \log n + n)$$. I guess though that reduces to $$O(n \log n)$$, but is that the best that we can do?

• There are two aspects, which you seem to be mixing up: (1) Given a list of words and their probabilities, determining which questions to ask; (2) Asking the questions until you identify the word. Almost any strategy you could think of for (1) manages to do (2) in $O(n)$ worst-case time; the question is, can it be done in less? If so, how to design (1) for that? Oct 9 at 23:16
• but if we have $O(n log n)$ for coming up with the questions (for example, by sorting) in (1) then even doing $O(n)$ in (2) maintains $O(n log n)$ right? @j_random_hacker Oct 9 at 23:38
• No, you're combining (adding) the two complexities when the question doesn't want you to. (If it did want you to, then the optimal solution would be $O(n)$: Do nothing at all for (1), and ask $n$ questions in any order for (2).) Oct 9 at 23:39
• en.wikipedia.org/wiki/Huffman_coding Oct 10 at 6:36
• Where did you encounter this? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Please edit your question to provide the proper references.
– D.W.
Oct 10 at 6:37