Question

What is the running time of the Huffman algorithm, if its implementation of the priority queue is done using linked lists?

(a) O(C)

(b) O(log C)

(c) O(C log C)

(d) O(C^2)

The question was posed to me in a national level competition.

This intriguing question originated from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II

Answer 1

Correct answer is (d) O(C^2)

The explanation is: If the implementation of the priority queue is done using linked lists, the running time of Huffman algorithm is O(C^2).