What is the time complexity of huffman coding?

Worst case O(n log n). Space complexity is O(n). Optimal among all prefix-free codes for the given frequencies.

Huffman coding

hard

Rare symbols end up deepest and get the longest codes. Every symbol sits at a leaf, so no code is a prefix of another - which is what makes the output decodable without separators.

Worst O(n log n)Space O(n)

Loading the huffman coding engine…

Where to go next

Binary heap

medium

An array pretending to be a tree.

Trie (prefix tree)

medium

The path is the key.

Activity selection

easy

Earliest finish time - and two plausible rules that fail.