recategorized by
23,493 views
94 votes
94 votes

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?

  1. Unsorted array
  2. Min - heap
  3. Sorted array
  4. Sorted doubly linked list
recategorized by

5 Answers

Best answer
138 votes
138 votes
$\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$
edited by
53 votes
53 votes

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.

edited by
32 votes
32 votes

This might help n(logn)^1/2

1 flag:
✌ Edit necessary (Ray Tomlinson “Min heap searching time will take O(n) time but here akshat is taken it O(logn)”)
8 votes
8 votes
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.
Answer:

Related questions