2.4k views

An algorithm performs (log N)1/2 find operations , N insert operations, (log N)1/2 delete operations, and (log N)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
retagged | 2.4k views

(log N)1/2 find N insert  (log N)1/2 delete (log N)1/2 decrease-key
Unsorted Array O(N (log N)1/2) O(N) O(log N)1/2) O(log N)1/2)
Min-heap O( N (log N)1/2) O(N log N) O( (log N)3/2) O( (log N)3/2)
Sorted Array O( (log N)3/2) O(N2) O(N (log N)1/2) O(N (log N)1/2)
Sorted doubly linked-list O(N (log N)1/2) O(N2) O( (log N)1/2) O( N(log N)1/2)

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.

selected by
Some confusion in this question

Min heap decrease key , time complexity should be $N\left ( log N \right )^{\frac{5}{2}}$

Sorted array delete should be $\left ( log n \right )^{\frac{1}{2}}$

because we already know delete and insert time of every element and decrease key operation is nothing but delete and then insert operation

So, if we multiply delete and insert operation we get decrease key, rt?

@srestha

Min heap decrease key , time complexity should be N (log N)3/2

No, it is not.

the decrease key operation in  MinHeap will take O(logN) for each element so in total it is (log N)3/2

as in question it says , " (log N)1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set " so log N * (log N) 1/2 = (log N)1+1/2  =  (log N)3/2

@srestha

Sorted array delete should be (logn)1/2

No, it is not the way .

Delete in sorted array done in O(n) for each element , now in question says " algorithm takes  (log N)1/2 delete operations, "

so O(n) * (log N)1/2 = N (log N)1/2

Hence Sorted array delete is N (log N)1/2

Why O( (log N)1/2)  for deletion in sorted linked list?? Because sorted linked list will take O(1) time to delete only if pointer is provided to the previous element where we want to delete??

I know it wont change the answer but still ....?

An algorithm performs (log N)1/2 find operations , N insert operations, (log N)1/2 delete operations,

means  total number of delete operations are (log N)1/2

now sorted linked list will take O(1) time to delete

total time = O(1) * (log N)1/2

= O (log N)1/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.

edited

Sorted Array  in N insert  O(N2), because to make room for 1 element worst case takes O(N) time and for N elements takes O(N2) time, rt?

Correct.
We're same minded people bro!

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.
+1 vote