1,154 views
1 votes
1 votes
how to find the comparision complexities in huffman coding algorithm?

2 Answers

2 votes
2 votes

I guess you are talking about complexity of huffman coding.

1.We have n keys,and we need to merge tree n-1 time to generate final tree.

2.we use min heap to store frequency of every node.

3.In ever iteration we find out top two min frequencies ------->logn time

4.Then we merge those two frequencies and insert in the tree again---->logn

we repeat this process n- 1 time,then total complexity of huffman coding is =(n-1)*(3logn)=O(nlogn)

Related questions

1 votes
1 votes
2 answers
2
Akash Kumar Roy asked Apr 26, 2018
3,944 views
what is Space complexity of Huffman coding?
1 votes
1 votes
3 answers
4
Parshu gate asked Nov 16, 2017
2,594 views
The following message is: GATE2018GAATTTEEEE22000011188What is the average length of bits required for encoding each letter using Huffman coding___?