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

To store the frequencies of the characters. Right?

---

Yes........

---

I think it should be O(1). Huffman Coding uses Min-heap and heapsort. Heapsort has O(1) space complexity. We don't include the space required to store the input in Space Complexity.

---

Space complexity does includes input space.

https://www.geeksforgeeks.org/g-fact-86/

Also,input will be array of characters along with frequencies.

Can we convert it to minheap inplace?

---

Space complexity = input + extra.

Hear input is n symble ----> o(n)

Extra is size of stack is --------> o( logn)

Space = n + long = o (logn)

---

Space = n + long = o (logn) .It is 0(n).May be typeo

Please tell how will we create min heap without extra space?

---

I didn't know the difference between auxiliary space complexity and space complexity. Thanks for sharing. And heapsort is inplace because of this:

https://stackoverflow.com/questions/22233532/why-does-heap-sort-have-a-space-complexity-of-o1

https://www.quora.com/What-is-the-space-complexity-of-heap-sort

---

"Space Complexity of an algorithm" means extra space(memory)  that is needed by the algorithm

https://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecture2.html

https://stackoverflow.com/questions/18686121/differences-between-time-complexity-and-space-complexity

---

Heap sort's space complexity should be O(logn). Right? As the algo uses max-heapify internally. And so stack records needed is O(logn)

---

@Akash , Good question ! 

Max-Heapify uses tail recursion because function call is at the end. Due to this tail recursion , it minimizes the space complexity of heap-sort to O(1).

So, Space Complexity of Heap-Sort is O(1).

To understand , how space complexity becomes O(1) using tail-recursion .

watch this  video and then apply max-heapify algorithm for the below example and observe the space complexity using stack method.

Max-Heapify Algorithm

Example

other link :- https://stackoverflow.com/questions/72209/recursion-or-iteration

2^nd thing is , we can also convert this recursive max-heapify procedure to iterative procedure which will take O(1) space.

---

@ankit

So if asked for Space Complexity in an exam, should we consider input size or not?!

---

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.