(IC 5.9) Computational complexity of arithmetic coding
Arithmetic coding is linear time in the length of the source message and the encoded message. Since the encoded message length is near optimal on average, the expected time is near optimal.
A playlist of these videos is available at:
• Information Theory