[10 points] Consider the following program: P.Initialize() initializes the data

Question

[10 points] Consider the following program: P.Initialize() initializes the data structures. P.Insert(x) inserts elements x in P. P.Maximum() returns the maximum element of P (without deleting it from P). P.Size() returns the number of elements in P. Analyze carefully the (asymptotic) running time of Program5 assuming that P is implemented as a Max-Heap. Note that the time for P.Insert() is dependent on the number of elements in P which changes over the running time of the algorithm. Operations P.Initialize() takes constant time. Show your work of how you obtained the time complexity.

Explanation / Answer

P.maximum() gives a time complexity of O(1) in case of max-heap. The top element is the maximum element in a max heap. So given the implementation either as a linked list or an array we just need to see the first element done with array as index 0 and in linked list as head->data. All the cases of best case, worst case and average case are the same for P.maximum.

P.insert() takes a time of O(log2n) to insert in the worst case. The worst case scenario would be we insert an element that is more than the maximum element in the heap. So now we need to bring it up changing it with its parent. Since heap is a complete binary tree, all the levels are full so if there are n elements in a heap there would be log2n levels in the tree. So we have to exchange elements of the log2n levels giving a total time complexity of O(log2n). Average case for insertion would take the same time but the best case would take O(1) time because, the element is the lesser as compred to the parent so it is not moved up at all or there is no elements in the heap.

P.size() time complexity depends on the data structure used to store the heap- can be done in array or linked list representation. But for the both of them the time complexity would be the same. For array we have to store the size of the heap in a variable. Whereas for linked list we dont need to store anything. So for array the time complexity of P.size() would be O(1) where as for linked list the size we would need to find out by traversing all the elements of the heap thus taking a time of O(n).

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.