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

pluies

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)

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)