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:

Search the symbol list at each node: O(n) time

Then take log_n branches

Total: O(n * log_n)

For the special case described in 2.71:

1. Encoding the most frequent symbol:

Search through symbol list: O(n) time

Take the first single branch, since it will be at the top of the list: constant

Total: O(n)

2. Encoding the least frequent symbol:

Search through symbol list at each level: O(n) time

Take the next branch, since we are only removing one node, it would be: O(n - 1)

Here's my take on this problem.

NB: This specifically refers to the

encode-symbolprocedure, which is a sub-procedure of the actualencode. If we were to extend the solution toencode, we'd have to multiply by an additionalnfor the entire message.For the

encode-symbolprocedure in 2.68:O(n * log_n)For the special case described in 2.71:

1. Encoding the most frequent symbol:

O(n)2. Encoding the least frequent symbol:

O(n^2)Sphinxsky

The above answer is not comprehensive enough.

For the

encode-symbolprocedure in 2.68:O(n * log_n)O(n^2)O(n * log_n)andO(n^2).