<< 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)