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

Encoding the most frequent element as per ex. 2.71 is a mere search into the symbol list, which is accomplished in O(n).

Encoding the least frequent element involves descending down the tree, with a search in the symbol list each time.

The complexity is O(n) + O(n-1) + ... + O(1), akin to O(n²).

Still not 100% sure of that; correct me if I'm wrong.

*given complexity of `member` / `element-of-set` function is O(n)

I think the solution depends on how encode-symbol is implemented. In an efficient implementation, only one branch need to be searched to find the most frequent symbol. And that branch only has one symbol. Therefore, to encode the most frequent symbol, the order of growth is actually O(1).

As for encoding the least frequent symbol, we need to search both left and right branches at every node. Since we need to search n-1 nodes, the order of growth is O(n) + O(n-1) + ... + O(1), which is O(n^2).

Note that the solution for most frequent symbol is true for all cases, while the solution for least frequent symbol is only true for the special case of 2.71.