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

@source_code rectified

---

Few key takeaways:

• Min heap takes O(n) for searching in worst case, like searching for max element in min. heap will take O(n/2)
• After deleting any element from sorted array, we've to swap every element by one position BUT this does not happen in unsorted array as we can swap the targeted element with last element and then delete the last element
• Cannot apply binary search on sorted doubly linked list

---

https://youtu.be/i_t7m8uQHds?si=eVSLRojukKXS_kZ3

one of the best

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

Keys drawn from a linearly ordered set

Whats the exact meaning of this? 

---

Can we think of it as because we have $N$ insert operations and $N>>>logN^{1/2}$ , the Data structure  that takes the least time for insert is the best one?
Here For insertion of N items, Unordered Array just takes N whereas all  other will take $\omega(N)$, thats the answer!

---

Sir insertion in sorted array takes O(N²) time

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
Amazing...
outstanding observation!

---

great observation!👍 btw its the actual concept 

---

@Rajesh Pradhan Sir Nice Observation. 

Thanks for sharing.

Answer 3

This might help n(logn)^1/2

Comments

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.

---

i dont thnk so, after removing the deeted eement we need to shift the elements too right else we wil have blank value.

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

---

i think this is the most sensible answer, think like if you've to implement a datastructure with the above functionalities then what will you chose and obviously usorted array will be the best

Answer 5

Here is the solution : 

Comments

But when array if fully filled then inserting a new element may take O(n) time, but still unsorted array is the best choice here.

Answer 6

For Unsorted Array

Find takes O(N) time as we have to scan all the elements so for $O(logN)$$^1$$^/$$^2$ find operations =O(N$(logN)$$^1$$^/$$^2$)

Insertion takes O(1) time as we will insert at the end of array so for O(N) insertions = $O(1)*O(N)=O(N)$

For Deletion a pointer is given so we will swap pointed element with last element and delete it which takes O(!) time, so for $O(logN)$$^1$$^/$$^2$ deletions = O(1)*$O(logN)$$^1$$^/$$^2$=$O(logN)$$^1$$^/$$^2$.

for Decrease Key a pointer is given so we can decrease key in O(1) time so for $O(logN)$$^1$$^/$$^2$ decrease key operations = O(1)*$O(logN)$$^1$$^/$$^2$=$O(logN)$$^1$$^/$$^2$.

in the same way analyse other data structures 

and then check table given by Arjun sir.

 Unsorted array is the answer