Space complexity of Huffman coding

Question

what is Space complexity of Huffman coding?

Answer 1

If we have n symble then  we need to store each Symble in Array so 

Space complexity = O(n)

Comments

Thank you for such a detailed explanation.  I understood the concept but what about Huffman coding's space complexity? Is it O(n) or O(1). According to my understanding, we need n extra space to keep track of frequencies of the characters. What is your opinion on that.

---

@Akhilesh ,

I have given the link of University of Texas where it is mentioned that :-

We often speak of "extra" memory needed, not counting the memory needed to store the input itself.

So, we should not have to consider the input size to find the space complexity of an algorithm.

@Akash ,it should be O(n) which you have already mentioned because we have to store frequencies of characters from the input file seperately in the array.

---

Does the input will not contain the elements array and its frequency as its input?

Answer 2

To obtain Huffman coding we use data structure called min heap. At the initial phase all the nodes has to be present in heap(satisfying min-heap property).

If there are n elements in tree then space complexity will be O(n) which is extra space required.