Exercise 2.72.  Consider the encoding procedure that you designed in 
exercise 2.68. What is the order of growth in the number of steps needed 
to encode a symbol? Be sure to include the number of steps needed to 
search the symbol list at each node encountered. To answer this question 
in general is difficult. Consider the special case where the relative 
frequencies of the n symbols are as described in exercise 2.71, and give 
the order of growth (as a function of n) of the number of steps needed 
to encode the most frequent and least frequent symbols in the alphabet.

————————————————————————————————————————————————————————————————————————

The code I wrote doesn't search the symbol list at each node, rather it 
speculatively builds each possible sequence, and returns either false or 
the sequence it has built.  I think it might be n log n.

In a distribution as in 2.71, the time depends on how the tree is 
constructed, since my encode-symbol checks the left branch first.  If 
the most frequent symbol is put in the left branch of the root (or if 
I altered encode-symbol to check the right branch first) then it would 
encode the most frequent symbol in constant time with respect to n.

If the most frequent symbol is on the right, and searching starts on 
the left, then most frequent symbol would actually be the slowest to 
encode.  However, this may not be as much of a pessimization as it 
sounds, since all the other symbols (which, taken together, are, in 
the limit, equally as frequent as the most frequent symbol) are sped 
up by an equal amount.