Discussion
What is the time complexity of Huffman Coding ?
Answer: B
Huffman coding takes O(N log N) time.
The algorithm builds the tree by repeatedly removing the two lowest-frequency nodes from a priority queue and inserting their merged node. With a binary heap each removal or insertion costs O(log N), and there are about N - 1 merges, giving O(N log N) overall.
O(N) is possible only if the frequencies are already sorted and a two-queue method is used, which is not the general case. O(N (log N)^2) and O(N^2) overstate the cost of the heap version.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development