GATE CSE 2015 Set 1 | Question: 40

Question

An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decrease-key operations on a set of data items with keys drawn from a linearly ordered set . For a delete operation, a pointer is provided to the record that must be deleted . For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

• A. Unsorted array
• B. Min - heap
• C. Sorted array
• D. Sorted doubly linked list

Comments

can someone explain why

with keys from a linearly ordered set

statement is given in the question? 

---

https://www.youtube.com/watch?v=w_hXSoP2DyE

---

Any one please explain what is the meaning of decrease key operation ?

Answer 1

$\small \begin{array}{|c|l|l|l|l|} \hline
&\mathbf{(\log N)^{\frac{1}{2}}} \text{ find} & \mathbf{N} \text{ insert} &  \mathbf{(\log N)^{\frac{1}{2}}} \text{delete} & \mathbf{(\log N)^{\frac{1}{2}}}  \text{decrease-key} \\ \hline
\text{Unsorted Array} & O(N (\log N)^{\frac{1}{2}}) &O(N) &O(\log N)^{\frac{1}{2}})&O(\log N)^{\frac{1}{2}})\\ \text{Min-heap} &O(N (\log N)^{\frac{1}{2}})&O(N \log N)&O(\log N)^{\frac{3}{2}})&O((\log N)^{\frac{3}{2}})\\ \text{Sorted Array} &O((\log N)^{\frac{3}{2}})&O(N^2)&O(N (\log N)^{\frac{1}{2}})&O(N (\log N)^{\frac{1}{2}})\\ \text{Sorted doubly linked-list} &O(N (\log N)^{\frac{1}{2}})&O(N^2)&O((\log N)^{\frac{1}{2}})&O(N (\log N)^{\frac{1}{2}})\\\hline \end{array}$

So, Unsorted array is the answer.

The operations given can be performed in any order. So, for Min-heap we cannot do the usual BuildHeap method.

Delete in unsorted array is $O(1)$ as we can just swap the deleted element with the last element in the array and delete the last element.

For sorted-doubly linked-list we cannot do binary search as this would require another array to maintain the pointers to the nodes.

Correct Answer: $A$

Comments

so for MIN-HEAP DELETION, we are just considering the cases wherein we need to just delete the minimum element and NOT the one pointed out by the pointer??

Because in that case, we’ll have to delete elements from min-heap and store it somewhere until we get the element pointed out by the pointer and then delete it and then insert back those elements which we initially deleted.

Am i right??

---

@Arjun sir, kindly explain why can't we use build heap method to do insertion in min heap here?

---

@Hira Thakur sir In sorted array to delete any desired no which is presnt in list we simply firstly search this element in arr in logn time then delete in O(n) time then total complexity should be taken as logn

but arjun sir taken in O(n ) why ?

Answer 2

I got the same table as Arjun sir got.

& Everybody must know that how it derived.

But I think for average mind like me it will time-consuming in exam.

I have one observation while I read this question.

Imp Note : I have Considered (find,insert,delete,dec-key) operations while giving ans.

Before and After doing operations on data structure x it is required that it should be data structure x only.Now replace x with given data structures.

So If it is a heap then after doing specified operations(find,insert,delete,dec-key) it should be heap only.

Means Heap Constraint need to be satisfied. Same phenomena applicable for other data structure.

So max time is consuming in fulfilling that constraint.

That's why Unsorted Array (where no such constraint) won the Race compare to Heap,Sorted array and Sorted doubly linked list which are truely structured.

So Option A. unsorted array is Ans.

PS:- 1. Plz verify my ans. And comment if u r not agree.

2. Must realize Arjun sir's Ans.

Comments

@Rajesh Pradhan

Great observation sir.

Thanks alot !

---

@Rajesh Pradhan
Amazing...
outstanding observation!

---

great observation!👍 btw its the actual concept 

Answer 3

This might help n(logn)^1/2

Comments

@Satbir

In case of  delete operation in doubly linked list .when we are given a pointer to the node to be deleted then we always consider swapping to be the default procedure .right?(which gives O(1) )

 

---

yes.

---

Why delete and decrease key operations for unsorted array is taking $O(n)$ time. Pointers are already provided for the items to be deleted or decreased. It should take $O(1)$. Therefore $\sqrt{logn}$ for both of them.

Answer 4

Answer : A

The time complexity of insert in unsorted array is O(1), O(Logn) in Min-Heap, O(n) in sorted array and sorted DLL.

Since number of insertion operations is asymptotically higher, unsorted array is preferred.

Comments

nt a correct explanation ...

---

Please explain the delete and decrease key operations of min heap