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(c2)

Question

Quizplus · Accepted Answer

The running time of the Huffman algorithm when implemented using a linked list for the priority queue is $O(c^2)$. This is because, in each iteration, finding and removing the two smallest elements and then inserting their sum back into the list takes $O(c)$ time, and since there are $O(c)$ iterations, the total time complexity becomes $O(c^2)$.

What Is the Running Time of the Huffman Algorithm, If