Consider the following program P Initialize initializes the

Consider the following program: P Initialize() initializes the data structures. P Insert (a) inserts elements a in P P Extract Max returns the maximum element of P and deletes it from P. P Size() returns the number of elements in P (a) Analyze carefully the running time of Program2 assuming that P is implemented as a Max-Heap. Analyze the total time for both the PInserto and PExtractMaxO operations. Note that the time for P. Insert and P.ExtractMaxO is dependent on the number of elements in P which changes over the running time of the algorithm. Operations P.InitializeO and P.SizeO take Show your work. (b) Analyze carefully the running time of Program assuming that P is implemented by some data structure which takes Theta (squarerrot x) time for P.Inserto where s is the number of elements in P and e(1) time for P.ExtractMaxO. Analyze the total time for both the P.Inserto and P.ExtractMaxO operations. Note that the time for P-Inserto is dependent on the number of elements in P

Solution

Probelm 1:

the heap has a complete binary tree structure, its height = lg n (where n is no of elements). In the worst case (element inserted at the bottom has to be swapped at every level from bottom to top up to the root node to maintain the heap property), 1 swap is needed on every level. Therefore, the maximum no of times this swap is performed is log n. Hence, insertion in a heap takes O(log n) time.

therefore

Block 1:

P.intialize() takes contant time

Block 2:

for i 1->n runs for O(n) times

for j 1->n runs for O(n) times

for k 1-> root(n) runs for O(root(n)) times

P.insert() takes O(log n) times

threfore overall is O(n^2*root(n)log n)

Block 3:

for i 1->n runs for O(n) times

for j 1->n runs for O(n) times

P.ExtractMax() takes O(log n) times

threfore overall is O(n^2*root(n)log n)

< ########################################################################### >

Problem 2:

Block 1:

P.intialize() takes contant time

Block 2:

for i 1->n runs for O(n) times

for j 1->n runs for O(n) times

for k 1-> root(n) runs for O(root(n)) times

P.insert() takes O(root(n)) times

threfore overall is O(n^3)

Block 3:

for i 1->n runs for O(n) times

for j 1->n runs for O(n) times

P.ExtractMax takes O(1)

threfore overall is O(n^2)

< ########################################################################### >

Problem 3:

Block 1:

P.intialize() takes contant time

Block 2:

for i 1->n runs for O(n) times

for j 1->n runs for O(n) times

for k 1-> root(n) runs for O(root(n)) times

P.insert() takes O(1) times

threfore overall is O(root(n)*n^2)

Block 3:

for i 1->n runs for O(n) times

for j 1->n runs for O(n) times

P.ExtractMax takes O(root(n))

threfore overall is O(root(n)*n^2)