What is the worst case runtime for the most efficient algorithm to build a huffman tree?

398 Views Asked by At

I've searched online everywhere and can't seem to find an answer to this. Given a sorted list of frequencies, what is the most efficient algorithm for creating a huffman tree and what would its big O worst case be?

1

There are 1 best solutions below

0
On

If you have the list of ordered frequencies then the basic greedy algorithm runs in linear time. You can't beat that (from an asymptotic perspective) since you have to process each node at least once.