<< Previous exercise (2.71) | Index | Next exercise (2.73) >>


Here's my take on this problem.

NB: This specifically refers to the encode-symbol procedure, which is a sub-procedure of the actual encode. If we were to extend the solution to encode, we'd have to multiply by an additional n for the entire message.

For the encode-symbol procedure in 2.68:

For the special case described in 2.71:

1. Encoding the most frequent symbol:

2. Encoding the least frequent symbol:

The above answer is not comprehensive enough.

For the encode-symbol procedure in 2.68:

    Consider the maximum and minimum
  • The minimum value is the case of a full binary tree:O(n * log_n)
  • The maximum value is like in 2.71:O(n^2)
  • The final answer is between O(n * log_n) and O(n^2).