What is the running time of Algorithm HuffmanX in terms of b

What is the running time of Algorithm Huffman(X) in terms of big-Oh as a
function of the number of letters ? Answer this question for the following 3 implementations
of priority queue Q. Briefly justify in each case

A. Priority queue Q implemented using a Sorted List.

B. Priority queue Q implemented using a Unsorted List.

C. Priority queue Q implemented using a Heap.

Algorithm Huffman(X):

Input: String X of length n with d distinct characters

Output: Huffman tree for X

1. Compute the frequency f(c) of each character c of X.

2. Initialize a priority queue Q

3. For each character c in X do {

4. Create a single-node binary tree T storing c

5. Insert T with key f(c) into Q }

6. While Q.size() > 1 do {

7. e1= Q.removeMin()

8. e2= Q.removeMin()

9. Create new binary tree newT with left subtree e1.tree and right subtree e2.tree

10. newFreq= e1.freq+e2.freq

11. Insert newT with key newFreq into Q }

12. e= Q.removeMin()

13. return e.tree

Solution

Let n be the number of letters

Case-A: Priority Queue implemented using a Sorted List

Line1 computes frequency f(c ) of n letters in O(n) times

Line2 initializes the Q in Sorted order .It takes O(nlogn) time .(any efficient sorting algorithm takes O(nlogn) time in worst case

The loop in line 3 to 5 runs n times , creates n trees with single node takes O(n) times.

The loop in line 6 to 12 removes two minimum node , store the frequency of two in ‘newFreq’ ,create a new node and insert new node with freq ‘newFreq’ back into the list.The loop runs exactly n-1 times.

In side the loop,

Each remove operation takes O(n) times , As it is a Sorted list, minimum element present in X(1). And to remove it, all element to the right A[1] is shifted to left. As there are n-1 such remove operations, In total it takes   (n-1)(n)=O(n^2) times

Insert Operation also takes O(n) operations as it inserts a new node with ‘newFreq’ into an already sorted List . As there are n-1 such Insert operations, In total it takes   (n-1)(n)=O(n^2) times

So in this implementation, The algorithm takes

O(n)+O(nlogn)+O(n)+O(n^2)+ O(n^2)= O(n^2) times

Case-B Priority Queue implemented using a UnSorted List

Line1 computes frequency f(c ) of n letters in O(n) times

Line2 initializes the Q with all the letters with frequence. Takes O(n) time. (No sorting required)

The loop in line 3 to 5 runs n times , creates n trees with single node takes O(n) times.

The loop in line 6 to 12 removes two minimum node , store the frequency of two in ‘newFreq’ ,create a new node and insert new node with freq ‘newFreq’ back into the list.The loop runs exactly n-1 times.

In side the loop,

Each remove operation takes O(n) times , As it is a unSorted list, to remove first find position of minimum node ,and on finding the position(pos) , shift all nodes to the right of ‘pos’ to left by one position. This scans all letters of the list exactly once.   As there are n-1 such remove operations, In total it takes   (n-1)(n)=O(n^2) times

Insertion Operation also takes O(1) operations as it inserts a new node with ‘newFreq’ by appending it in the list in (Q.size+1 position) .(Note that Q,size is decreased by one on each remove Operation and increase by one on Insert operation). As there are n-1 such Insert operations, In total it takes   (n-1)(1)=O(n) times

So in this implementation, The algorithm takes

O(n)+O(n)+O(n)+O(n^2)+ O(n)= O(n^2) times

Case-C : Priority Queue implemented using a Heap

Here we use a MinHeap

Line1 computes frequency f(c ) of n letters in O(n) times

Line2 initializes the Q . It takes O(n) time using BUILD_MIN_HEAP (check pseudo code BUILDMAXHEAP , chapter HeapSort,author T.Coreman et al “Introduction to algorithim)

The loop in line 3 to 5 runs n times , creates n trees with single node takes O(n) times.

The loop in line 6 to 12 removes two minimum node , store the frequency of two in ‘newFreq’ ,create a new node and insert new node with freq ‘newFreq’ back into the list.The loop runs exactly n-1 times.

In side the loop

Each remove operation takes O(logn) times , As it use a Min Heap . Minimum node presents at 1^st position in the heap. Removing an item requires exchange of X[1] and X[heapsize] and the MinHeapifying the altered heap, which requires O(logn) time   (see MAXHEAPIFY procedure in above mentioned book). As there are n-1 such remove operations, In total it takes   (n-1)(logn)=O(nlogn) times

Insert Operation also takes O(nlogn). As it adds the new node at the end of the min Heap and then it traverses the path from this node to parent by following the the parent node and inserting the node it its proper place. In worst case number of node present in a path from leaf to root is O(height of the tree) which is O(logn). As there are n-1 insertion operations, it takes (n-1)(logn)=O(nlogn) times

So in this implementation, The algorithm takes

O(n)+O(n)+O(n)+ O(nlogn) + O(nlogn) = O(nlogn)   times